筛法参考
埃氏筛
const int N=1e8+6;
bool vis[N];
void prime(int n){
vis[1]=1;
for(int i=2;i*i<=n;i++){
if(vis[i]==0){
for(int j=i*i;j<=n;j+=i)
vis[j]=1;
}
}
}
线性筛(欧拉筛)
bool vis[N];
int prime[N];//prime[0]表示素数个数
void Prime(int n){
for(int i=2;i<=n;i++){
if(!vis[i]) prime[++prime[0]]=i;
for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}