质数的两种筛法（我也不知道为啥少一种）

埃筛

bool prime(int x){
	if(x==1) return 0;
	for(int i=2;i*i<=x;i++) if(x%i==0) return 0;
	return 1;
}

线性筛

void prime(){
    vis[0]=vis[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i]) p[num++]=i;
        for(int j=0;j<num&&i*p[j]<N;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}

质数的两种筛法（我也不知道为啥少一种）

原文：https://www.cnblogs.com/RevolutionBP/p/15168346.html