素数筛选

代码1： #include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #include<vector> #include<queue> #include<stack> #include<iostream> #include<string> #include<algorithm> using namespace std; #define MaxSize 100 #define inf 0x3f3f3f3f int main() { int prime[MaxSize]; memset(prime,0,sizeof(prime)); prime[0]=prime[1]=1;//0和1不是质数，标记为1 for(int i=2; i<MaxSize; i++)//目的是找合数 { if(prime[i]==1) continue;//不是质数就跳过 if(i*i>MaxSize) continue;//注意如果MaxSize太大的话，i*i可能超int，那就写成i>MaxSize/i for(int j=i*i; j<MaxSize; j+=i)//如果是5，就标记5*5 ~ 5*n。那5*3怎么办呢？之前找到3的时候，3*3 ~ 3*n当中已经找到过了，所以就不找了 { prime[j]=1; } } for(int i=0; i<MaxSize; i++) { if(prime[i] == 0) printf("%d\n",i); } return 0;

代码2：

memset(prime,0,sizeof(prime)); prime[0]=prime[1]=1; for(int i=2; i<MaxSize; i++) { for(int j=2; j*j<i; j++) { if(i%j==0) prime[i]=1;//合数 } } for(int i=0; i<MaxSize; i++) { if(prime[i] == 0) printf("%d\n",i); } return 0;

代码3：这样可以prime直接保存它角标的最大质因数,讲道理，这种更好，毕竟还能保存除了是否为质数以外的其他信息。

prime[0]=prime[1]=1; for(int i=2; i<MaxSize; i++) { if(prime[i]==0)//合数就不用考虑了，因为它的质因数在翻倍的时候肯定能包括这个合数的倍数。比如合数为4，它之前就刷过的质因数2的倍数2,4,6,8,10,12……一定能包括4的倍数4,8,12…… { for(int j=i; j<MaxSize; j+=i) { prime[j]=i; } } }