一般筛法求素数代码
思路:素数的倍数不是素数。
#include<iostream> using namespace std; const int M = 2000000; int a[M] = {1,1}; int prime[M]={0}; int k=0; void init() { for(int i=2;i<=M;i++) { if(!a[i]) { prime[k++] = i; for(int j=i+i;j<=M;j+=i) a[j]= 1; } } } int main() { int n; while(cin>>n) { for(int i=0;i<n;i++) cout<<prime[i]<<" "; cout<<endl; } }
快速线性筛法
原理:1.一个合数是由n个素数的乘积所组成的
2.素数的倍数不是素数。
建议无论手模拟一个两个过程 就明白谁原理和优势了。
#include<iostream> using namespace std; const int Max=2000000; long long prime[Max] = {0}; int k=0; int a[Max]={1,1}; void init() { for(long long i=2;i<Max;i++) { if(!a[i])// prime[k++] = i; for(long long j=0;j<k&&i*prime[j]<Max;j++) { a[i*prime[j]] = 1; if(i%prime[j]==0)// break; } } } int main() { int n; init(); while(cin>>n) { for(int i=0;i<n;i++) cout<<prime[i]<<" "; cout<<endl; } }
推荐:http://blog.csdn.net/dinosoft/article/details/5829550