欧拉筛法（线性筛素数）

欧拉筛法，一种可以在线性的时间复杂度内筛出素数的算法。

算法思路

对于每一个数（无论质数合数）x，筛掉所有小于x最小质因子的质数乘以x的数。比如对于77,它分解质因数是7*11，那么筛掉所有小于7的质数*77，筛掉2*77、3*77、5*77。

代码

//vis[]   记录一个数是否被访问过的数组
//cnt0    素数计数器
//prime[] 最后所有筛出来的素数都会进到这个数组里面
//MAXN    上限

//准备工作
vis[0]=1;
vis[1]=1;
cnt0=0;

for(int i=2;i<=MAXN;i++){
	if(!vis[i]) prime[++cnt0]=i; //若是这个数还没被访问过，则说明是素数，加入prime[]
    
	for(int j=1;j<=cnt0;j++){  //从已经筛出来的素数里面开始筛选，保证从小到大
		if(i*prime[j]>MAXN) break;  //越过上限，而且后面的数必比他大，跳出循环
		vis[i*prime[j]]=1;  //筛掉所有小于i最小质因子的质数乘以i的数
		if(i % prime[j] == 0) break;  //到达最小质因数，后面的数必比他大，跳出循环
	}
}

参考&证明

https://www.cnblogs.com/jason2003/p/9761296.html