今天发现了一个更快的素筛，比以前会的素筛速度快了整整一倍，虽然大部分题目不会对时间要求那么严格，但是会一个更快的算法还是很棒的。
以前用的素筛：
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int maxn=(1<<24)+1; bool isprime[maxn+5]; int prime[maxn+5],cnt=0; void get() { for(int i=2;i<=maxn;i++) { if(!isprime[i]) { prime[cnt++]=i; for(int j=i+i;j<=maxn;j+=i) isprime[j]=1; } } } int main() { get(); cout<<cnt<<endl; printf("%d %d %d\n",prime[0],prime[1],prime[2]); return 0; }
更快的素筛：
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int maxn=(1<<24)+1; bool isprime[maxn+5]; int prime[maxn+5],cnt=0; void get() { for(int i=2;i<=maxn;i++) { if(!isprime[i]) prime[cnt++]=i; for(int j=0;j<cnt&&i*prime[j]<=maxn;j++) { isprime[i*prime[j]]=1; if(i%prime[j]==0) break; //注意这两句话的顺序 } } } int main() { get(); cout<<cnt<<endl; printf("%d %d %d\n",prime[0],prime[1],prime[2]); return 0; }
原文：http://www.cnblogs.com/Ritchie/p/5862824.html