线性筛

欧拉筛很简单，所以文章很短。

核心思想：每个数尽量只被筛一次

算法核心要点：

筛法，顾名思义，筛去所有不合法的，留下得就是合法的。

要筛出来素数，就是要筛去所有合数。

为了尽量不重不漏的枚举合数，我们就要发现每个合数唯一的特征来做到去重，
（这里“唯一的特征”在去重的思想中很常见）

于是以每个合数最小的素因数为这个特征，因为显然的，每个合数都有且只有唯一的一个“最小的素因数”。

那么每个合数都可以被唯一地分解成它最小的素因子×一个大于一且小于自己的数

形式化的，如果$m$是合数，那么$m$一定可以被唯一的分解成$p \times i$（$p \in \mathbb{P}，1<i<m$ ），其中$p$小于等于$i$的所有素因子。

我们如果能保证枚举的$p$和$i$不重复，那么就可以保证每个数都只被筛一次。

于是我们枚举$i$，再枚举对于$i$所有合法的$p$，就能枚举出所有的合数$m$，做到线性筛。

int prime[MAXN],tot=0;bool vis[MAXN];
void Euler_sieve(int n){
    for(int i=2;i<=n;i++){//            ......(1)
        if(!vis[i])prime[++tot] = i;//没被标记过，是素数
        for(int j=1;j<=tot;j++){
            if(i * prime[j] > n)break;//不用筛界外的数
            vis[i * prime[j]] = true;//            ......(2)
            if(i % prime[j] == 0)break;//已经枚举到i的最小素因子了，剩下的以后会筛到
        }
    }
    return ;
}
/*
复杂度证明：
（1）代码中第一层循环将 每个数 至少访问一遍
（2）第二层循环会不重复的把每个 合数 多标记一遍
于是复杂度为 O(c * n) , 1 < c < 2 。
*/