筛法求素数

level1:最原始的求素数方法

话不多说直接上代码（就是教科书上的）

#include <stdio.h> #include <math.h> int IsPrime(int x); int main() { int i,n; scanf("%d",&n); for(i=1;i<=n;i++) { if(IsPrime(i)) printf("%d\n",i); } return 0; } int IsPrime(int x) { int k,i; k=(int)sqrt(x); if(x<=1) return 0; for(i=2;i<=k;i++) { if(x%i==0) return 0; } return 1; }

level2:一般线性筛法

基本思路：先把某个范围的数全当成是素数，然后先给定0,1,不是素数。然后显然2就是最小的素数了，就是从2开始判定的。2是素数，先保存起来，那么2的倍数都不是素数了，标志为0.依次类推

3.4.5……. （注意这里面2的倍数有个技巧是从 i2 开始而不是 i*2）

#include <iostream> #include <cstdio> #include <cstring> using namespace std; void Prime(int n); int main() { int n; scanf("%d", &n); Prime(n); return 0; } void Prime(int n) { int prime[n+10], cnt = 0; bool mark[n+10]; memset(mark, 1, sizeof(mark));//标记为0代表不是素数,1代表是素数。 memset(prime, 0, sizeof(prime));//素数存储的地方 mark[0] = 0; mark[1] = 0; //核心代码----------------------- for(int i=2; i<=n; i++) { if(mark[i]) { prime[cnt++] = i; for(int j=i*i; j<=n; j+=i) { mark[j] = 0; } } } //------------------------------ for(int i=0; i<cnt; i++) { printf("%d\n", prime[i]); } }

level 3:快速线性筛法

仔细分析可以发现第二种方法会造成重复筛除合数，影响效率。比如10，在i=2的时候，k=2*15筛了一次；在i=5，k=5*6 的时候又筛了一次。所以，也就有了快速线性筛法。

分析： 利用了每个合数必有一个最小素因子。每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。 代码中体现在： if(i%prime[j]==0)break; prime数组 中的素数是递增的,当 i 能整除 prime[j]，那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉。 因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。 在满足i%prme[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。

#include <iostream> #include <cstdio> #include <cstring> using namespace std; void Prime(int n); int main() { int n; scanf("%d", &n); Prime(n); return 0; } void Prime(int n) { int prime[n+10], cnt = 0; bool mark[n+10]; memset(mark, 1, sizeof(mark));//标记为0代表不是素数,1代表是素数。 memset(prime, 0, sizeof(prime));//素数存储的地方 mark[0] = 0; mark[1] = 0;//这两个肯定不是素数了 for(int i=2; i<=n; i++) { if(mark[i])//是素数就存起来 { prime[cnt++] = i; } for(int j=0; j<cnt && i*prime[j]<=n; j++) { mark[i*prime[j]] = 0; if(i % prime[j] == 0) break; } } for(int i=0; i<cnt; i++) { printf("%d\n", prime[i]); } }

拓展阅读： 较易懂的解释 较准确的解释

ReCclay 认证博客专家 嵌入式软件开发 机器/深度学习 全栈技术学习者 大家好，我是博主ReCclay，目前处于研究生阶段，就读于电子科技大学，主攻方向为汽车辅助驾驶算法研究。入站以来，凭借坚持与热爱，以博文的方式分享所学，截止目前累计博文数量达800余篇，累计受益人次达130w+次，涉及领域包括但不限于物联网开发、单片机开发、Linux驱动开发、FPGA开发、前/后端软件开发等。在未来我将继续专注于嵌入式相关领域，学习更多的科技知识，输出更高质量的博文。