算法介绍：欧拉筛法是在O（N）线性时间内实现素数筛选的优秀算法。

算法思路：总体上与Eratosthenes筛法类似，也是用较小的数筛去较大的合数。

关键思路在于：每一个合数都保证是被其最小的质因子筛去的，下简称称该条件为线性条件。

结合代码分析：

inline void Euler_Sieve(){
    for(register int i=2;i<=n;i++){
        if(isPrime[i]) pri[++cnt]=i;
        for(register int j=1;j<=cnt&&i*pri[j]<=n;j++){
            isPrime[i*pri[j]]=false;
            if(i%pri[j]==0) break;
        }
    }
}

对每一个数i，无论其是否为质数，都可以用其筛去其他数。

j 循环到 i % Prime[j] = 0就恰好需要break的理由是：

设1<=s<j<t

证明：若最小质因子比pri[j]小，则在循环到j之前就已break，不可能循环至pri[j]。

证明：引理1已证i的最小质因子为pri[j]，故i*pri[j]最小质因子也应为pri[j]。引理2保证了被pri[j]筛掉的所有合数都满足线性条件。

证明方法如引理1。引理3保证了j之前所有被筛掉的合数都满足线性条件。

证明方法：由引理1可易证。故若j继续循环增大，则i*pri[t]将被pri[t]筛掉，但pri[t]并非其最小质因子，故不满足线性条件，故需break。

综上，当i%pri[j]==0的时候实行break操作可保证满足线性条件，实现线性筛。