线性筛
线性筛的理解和应用
最近在准备相关算法竞赛，正好班里有写博客的活动，就在此记录下自己菜不成声学习的过程。>v<
为算出小于等于n的素数的个数，较自然也是最暴力的的方法便是对每个小于n的正整数进行判定，这样的方法显然达到最优的复杂度，暴力硬解的结果无疑是最终喜提“Time Limit Exceeded”。
为提高算法效率，就要引入“筛”的思想——主要思想是：我们选出一个数n时无论n是素数还是合数，2n,3n,..都是合数，我们无需对这类数进行是否为素数的判断。
Eratosthenes 筛法 （埃拉托斯特尼筛法，简称埃氏筛）
埃氏筛算法的主要思想是：如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。具体算法如下：
int Eratosthenes(int n) {
int p = 0;
for (int i = 0; i <= n; ++i) is_prime[i] = 1;
is_prime[0] = is_prime[1] = 0;
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
prime[p++] = i; // prime[p]是i,后置自增运算代表当前素数数量
for (int j = i * i; j <= n;
j += i) // 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i
// 的倍数开始，提高了运行速度
is_prime[j] = 0; //是i的倍数的均不是素数
}
}
return p;
}埃氏筛通常可以称为普通筛，结构比较简单，也比较容易理解，其核心就是对找到的素数的倍数通过一次循环进行标记，虽然要额外占用O(n)的内存空间保存标记，但非常高效地减少了程序复杂度。
我们应该注意到，埃氏筛在对数字进行标记筛选时，存在重复筛选，比如6既可以被2筛掉，又可以被3筛掉。原因：任意一个整数可以写成一些素数的乘积
其中p1<p2<p3，这样这个数n能被p1,p2和p3筛掉,反复被标记，尤其在n比较大的时候，n可能有相当多个素因子，被多次标记，显然浪费了时间。
Euler筛法(线性筛)
基于普通筛的不足之处，Euler对其做出了修改——直观地来说，当我们用埃氏筛法对一个素数的n倍进行筛选时，若正在被标记的这个倍数已经足够大，大到超过一特定的数字后，那这个数一定有更大的素因子，能在后续过程中再次被标记，此时就可以停止循环，算法继续对下一个未标记的数进行是否为素数的判断。
通过观察不难发现，若当前正在处理n的i倍数in，i能整除n，那么i与下一个要进行筛选的数的乘积这个合数肯定会被n乘以某个数提前筛掉。因此这里的i便是我们要找的“特定的数字”，利用这一数字提前break掉循环，可以使得每个数字均被筛选一次，将时间复杂度降到最低，这也就是Euler筛的算法思想，实现代码如下所示。
void init() {
phi[1] = 1;
for (int i = 2; i < MAXN; ++i) {
if (!vis[i]) {
phi[i] = i - 1;
pri[cnt++] = i;
}
for (int j = 0; j < cnt; ++j) {
if (1ll * i * pri[j] >= MAXN) break;
vis[i * pri[j]] = 1;
if (i % pri[j]) {
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
} else {
// i % pri[j] == 0
// 换言之，i 之前被 pri[j] 筛过了
// 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
// pri[j] 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break
// 掉就好了
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
}
}
}关键之处在：if(i%prime[j]==0) break;
这句代码保证了每个数最多被筛一次，将时间复杂度降到了线性。
证：prime[]数组中的素数是递增的,当i能整除prime[j]，那么iprime[j+1]这个合数肯定会被prime[j]乘以某个数筛掉。因此，这里直接break掉，将iprime[j+1]及之后的给后面的数去筛。这种方法能保证每个数只被筛一遍，又能保证每个数都被筛到。
为了更好的理解，画出前面几次筛的情况:
一般来说，当筛选范围n较小时，埃氏筛和欧氏筛复杂度较相近，甚至埃氏筛表现更好，但随着n的增大，欧氏筛的优越性也逐渐体现出来，可以达到埃氏筛3-4倍的速度。
参考：
