//欧拉筛模版 const int maxn=1e6+7; int vis[maxn]; int prime[maxn]; //最后prime数组里面储存的是所有的素数,从小到大排列 void init() { int cnt=0; vis[0]=vis[1]=1; //1代表不是素数,0代表是素数 for(int i=2;i<=1e5;i++) { if(vis[i]==0) prime[cnt++]=i; for(int j=0; j<cnt && i*prime[j]<=maxn ; j++) { vis[i*prime[j]]=1; //欧拉筛模板 if(i%prime[j]==0) break; } } }