c++线性素数筛模板

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N=10000001;
int vis[N];
int prime[N];
int cnt;
int main(){
	int i,j;
	for(i=2;i<N;i++){
		if(!vis[i]){
			prime[cnt++]=i;
		}
		for(j=0;j<cnt&&i*prime[j]<=N;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0) break;//关键保证合数被较小的素数筛出后不再重复 
		}
	}
	for(i=2;i<N;i++)
	if(!vis[i])
	printf("%d\n",i);
	return 0;
}