欧拉线性筛法（求质数）

欧拉筛法的基本思想 ：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。
代码 ：

int prime[maxn];
int visit[maxn];
void Prime(){
    mem(visit,0);
    mem(prime, 0);
    for (int i = 2;i <= maxn; i++) {
        cout<<" i = "<<i<<endl;
        if (!visit[i]) {
            prime[++prime[0]] = i;      //纪录素数， 这个prime[0] 相当于 cnt，用来计数
        }
        for (int j = 1; j <=prime[0] && i*prime[j] <= maxn; j++) {
//            cout<<"  j = "<<j<<" prime["<<j<<"]"<<" = "<<prime[j]<<" i*prime[j] = "<<i*prime[j]<<endl;
            visit[i*prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

对于visit[i*prime[j]] = 1 的解释： 这里不是用i的倍数来消去合数，而是把 prime里面纪录的素数，升序来当做要消去合数的最小素因子。

发现i在消去合数中的作用是当做倍数的。
对于 i%prime[j] == 0 就break的解释 ：当 i是prime[j]的倍数时，i = kprime[j]，如果继续运算 j+1，iprime[j+1] = prime[j]kprime[j+1]，这里prime[j]是最小的素因子，当i = kprime[j+1]时会重复，所以才跳出循环。
举个例子 ：i = 8 ，j = 1，prime[j] = 2，如果不跳出循环，prime[j+1] = 3，83 = 243 = 2*12，在i = 12时会计算。因为欧拉筛法的原理便是通过最小素因子来消除。
--------------------- 
作者：彤云望月 
来源：**** 
原文：https://blog.****.net/qq_39763472/article/details/82428602 
版权声明：本文为博主原创文章，转载请附上博文链接！