线性筛
初始时，假设全部都是素数，当找到一个素数时，显然这个素数乘上另外一个数之后都是合数
把这些合数都筛掉，即算法名字的由来。但仔细分析能发现，这种方法会造成重复筛除合数，影响效率。
1
2
3
4
5
6
7
8
9
10
11
| int pri[N+9>>1],now;
bool vis[N+9];
void init(){
for(int i=2;i<=N;i++){
if(!vis[i])pri[++now]=i;
for(int j=1;j<=now&&pri[j]*i<=N;j++){
vis[pri[j]*i]=1;
if(i%pri[j]==0)break;
}
}
}
|