素数筛

埃氏筛法

const int max1=1e7; int prime[max1+1]; bool visit[max1+1]; int E_sieve(int n) { for(int i=0; i<=n; i++) { visit[i]=false; } for(int i=2; i*i<=n; i++) { if(!visit[i]) { for(int j=i*i; j<=n; j=j+i) { visit[j]=true; } } } int k=0; for(int i=2; i<=n; i++) { if(!visit[i]) prime[k++]=i; } return k; }

线性筛

const int max1=1e7; int prime[max1]; int visit[max1]; void Prime(int n) { memset(prime,0,sizeof(prime)); memset(visit,0,sizeof(visit)); for (int i = 2; i <= n; i++) { if (!visit[i]) { prime[++prime[0]] = i; //纪录素数， 这个prime[0] 相当于 cnt，用来计数 } for (int j = 1; j <=prime[0] && i*prime[j] <= n; j++) { // cout<<" j = "<<j<<" prime["<<j<<"]"<<" = "<<prime[j]<<" i*prime[j] = "<<i*prime[j]<<endl; visit[i*prime[j]] = 1; if (i % prime[j] == 0) { break; } } } }