论求质数算法的多种境界之线性筛法

✦前言

编程随想曾经写过一篇文章，大体列出了求质数的N种境界。
这篇文章中提出了筛法，但仅限于埃拉托斯特尼筛法。埃拉托斯特尼筛法是由公元前250年左右的一名古希腊大牛埃拉托斯特尼发明的。它朴素却巧妙，简单却快速。
等等，快速？我们可以通过观察知道，每个合数并不是只被筛一次，而是会被这个合数的每一个质因数筛一次。事实上，埃拉托斯特尼筛法的复杂度为O(n log log n)。（基本操作为标记一次合数，问题规模为筛法应用的范围。）
也许我们可以更快一些。假如表内的任何一个合数都只被筛去一次，那么算法的时间复杂度就可以降为O(n)了。
实际上，早在18世纪，数学大牛欧拉在他的一篇名为《无穷级数的一些检视》的论文中就提出了一种更优的筛法，能保证给定范围内的所有合数都能被恰好筛出一遍。根据这种方法的发明者命名，这种筛法就叫做欧拉筛法。
而在20世纪70年代，一篇ACM论文重新发明了这个方法，并证明出它的时间复杂度的确就是O(n)。因为这种筛法的时间复杂度是线性的，所以它又叫做线性筛法（我更喜欢这个名字）。
捎带一个小知识：欧拉的《无穷级数的一些检视》对数学界最大的贡献在于它提出了欧拉乘积公式（描述了Zeta函数与质数间的关系），为数论的研究提供了一个新的方向。

✦伪代码

bool sieve[2 ~ 范围] // 筛，默认未被标记的数都是质数
list primes // 质数槽
for i in 2 ~ 范围: // 作为倍数
    if sieve[i] = false: // 若这个数没有被干掉
        primes.append(i) // 加进质数槽里
    // 判断i是否加入质数槽并处理的部分要放在遍历之前
    for j in primes: // 从小到大遍历质数槽内的所有质数，作为最小质因数
        if j*i > 范围: // 超范围就没有标记的意义了
            break // 跳出
        sieve[j*i] = true // 干掉质数的非1正整数倍
        if j|i: // 如果j能整除i
            break // 跳出，保证j是被干掉数的最小质因数

✦原理

根据算术基本定理，每个合数都可以唯一地分解为若干个质数的乘积。我们挑出最小的那一个，将剩余的乘到一起，这样我们就得出每个合数都可以唯一地用它最小质因数的非1正整数倍（为方便表述不妨称最小质因数为p，倍数为a，易证p一定小于等于a）表示。
外循环在线性筛法中担任了两个作用：一个是令i作为被筛合数的a，另一个则将已经筛出的质数（算法保证当外循环遍历到i时i已经可以确定是否为质数，见下）加入质数槽中。
内循环则将质数槽内所有p（算法保证质数槽内一定包含所有的p，见下）对应的p与a的乘积标记上。
这样，范围内每个合数就都恰好被标记了一次。这就是线性筛的原理。

◇为什么当外循环遍历到i时i已经确定是否为质数？

当i为质数时

因为i不可能被标记，而i在筛中默认是质数，所以i可以确定为质数。此时，i会被加入质数槽中。

当i为合数时

i可以表示为p和a的乘积，而p小于等于a，p和a又小于i。当外循环遍历到p时，p会被加入质数槽中，而外循环遍历到a时，p*a（也就是i）会被标记（p可以等于a，此时p首先会被加入质数槽，然后p*a会被标记）。所以当i为合数时，i一定会被标记，因此i可以确定为合数。

◇为什么质数槽内一定包含所有的p？

因为当外循环遍历到i时i已经可以确定是否为质数，是质数的都会被加入质数槽中，所以质数槽包含从2到i所有的质数。
又因为所有的p都小于等于a（在这里是i），所以质数槽内一定包含所有的p。

✦总结

线性筛是一种非常巧妙的算法。在实际面试中，可以不要求应聘者写出该算法的细节，只要他能提到有这么一种筛法就行了（毕竟面试又不是OI）。