素数筛选（欧拉筛和埃氏筛）

1.埃氏筛 每个素数的倍数标记为合数

#include<bits/stdc++.h> using namespace std; int main() { clock_t startTime,endTime; startTime = clock(); int n; cin>>n; int *isPrime = new int[n+2]; memset(isPrime,1,n+2);//将所有数字初始为质数1 for(int i=2;i*i<=n;i++) { if(isPrime[i]==0)//处理过的不再处理 continue; for(int j = i*2;j<=n;j+=i) { isPrime[j]=0;//质数的倍数为合数 } } for(int i=2;i<=n;i++) { if(isPrime[i]) cout<<i<<" "; } endTime = clock();//计时结束 cout << "The run time is: " <<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl; return 0; }

2.线性筛（欧拉筛）对于每个数，我们只用它最小的质因子去筛掉它，因此每个数只会被筛掉一次，从而保证该筛法为线性的

#include<bits/stdc++.h> using namespace std; #define N 10000 int main() { clock_t startTime,endTime; startTime = clock(); //prime数组存放素数集合 //flag[i]数组标记i是否为素数，是标记为0，不是标记为1 int prime[N+1],flag[N+1]; //标记已筛选出的素数的个数 for(int i = 0;i<=N;i++) flag[i] = 0; int cnt=0; //flag[2]=0; for(int i = 2;i<=N;i++) { if(flag[i]==0) { prime[cnt++] = i; } for(int j = 0;j<cnt&&i*prime[j]<=N;j++) { flag[i*prime[j]] = 1; if(i%prime[j]==0) break; } } for(int k = 0;k<cnt;k++) { cout<<prime[k]<<" "; } endTime = clock();//计时结束 cout << "The run time is: " <<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl; return 0; }