素数筛选算法

全文概要

最近学习了一种筛素数的方法，能够以时间复杂度O(n)，即线性时间完成。一开始不能理解其中的一句话，搜索了很久，大部分结果都是一群人在网上卖萌。好好思索了一番，按照自己的思路终于理解了。本文的内容绝不卖萌，但也难称严谨，仅以备忘，欢迎斧正。

暴力法

没接触这种方法之前，如果面试官让我筛一下素数，即给定上限 $n$，找出从 $1$ 到 $n$ 之间所有的素数/质数) 我大概率会说：(作谦虚状)好的，我尽力试一试。 其实心里暗喜：嗯，很轻松嘛，然后不假思索写下…

就像这样：

正准备提交时，突然听到对面一声叹息…不经意望去，对方面露鄙夷，心觉不妙… 再看看自己刚写的代码，我的天！遍历？？？还可以更low一点吗…估计此时面试官和我都想问同一个问题：你到底有没有学过算法？

于是两秒钟的自我检讨之后，赶紧改了上面代码的几个判断条件，成了这样：

嗯…至少不用遍历，对每个数只用检查到其平方根，另外还可以要判断的数从3开始每次加2可以跳过全部偶数，因为偶数肯定不是素数啦，运算次数是降低了不少，可复杂度不还是 $O(n^2)$ 吗？

不对…对面那家伙脸色不太好，好像更加不耐烦了…怎么办，不慌不慌…

筛法

于是，我再度埋下头，看起来像是在认真思考，其实只是不敢直视对方…

哎，慢着！灵机一闪，思绪回到了大二算法课上，老师讲过一种叫做“筛法”的东东，不过好像记不太清了，我再想想…

半分钟后…

回来了，我感到它们全都回来了！

拍拍脑袋后奋笔疾书，筛法跃然纸上：

这会儿人自信多了，压箱底的老本被翻了出来，总不能有差了，直勾勾地望向面试官，只见他面色稍宽，眉宇间仍透露着几分不满，说道：我看你换了几种算法了，前面的就不说了，给你一个大数据的场景，比如1~1000000的范围，输出其中的素数，你这种筛法的时间性能还能看嘛？

嗯…毫不留情，莫非还有更优的算法？

“您容我再想想哈～”，陪着笑脸说完，双手抱头痛苦思考状/(ㄒoㄒ)/~~ 我的神呐…还有啥，还能怎么筛？

（以下纯属脑洞） 闭上眼睛思考的间隙，我去到未来，也就是现在啦，学会了这种线性筛素数的方法。

╭(╯^╰)╮哼！等我回来，甩你一脸，叫你不耐烦！没(T)错(T)！说的就是你！

线性筛法

贫了半天，不废话了，直接上代码，据说是某搞OI的大神写出来的，来源已无从考证：

以上算法其实有个名字，即欧拉筛法，专门用于筛选素数，思想也不复杂：当一个数为素数的时候，它的倍数肯定不是素数。所以可以从2开始通过乘积筛掉所有的合数，将所有合数标记，保证不被重复筛除，时间复杂度为 $O(n)$，由于它复杂度是线性的，所以特别适合于大数据量的场景。

咋一看，算法阐述起来和普通的筛法并无二致，实际上，两者最重要的区别就在于：

有无重复筛除？

为什么有这个问题呢？我们不妨回顾一下：

在普通筛法中，假设当前访问到一个素数2，那么接下来就会将指定范围内的2的倍数全部标记为非素数，比如 $6=2times3$，即在当前访问到的素数为2时，6会被2筛除。当2的倍数被筛除完毕，应该访问下一个素数3，而 $6=3times2$，即6也会被3筛除，这就造成了重复筛除，使得普通筛法的时间复杂度无法达到线性。

那么，欧拉筛法是如何做到不重复的筛除呢？一句话概括就是：

每个数都只按不超过其最小质因数的质数来筛除其倍数

比如2，其最小质因数为2，不超过2的质数只有2一个，因此，遍历到2时就只会筛除 $2times2=4$，而不会筛除6，10，14等更大的2的质数倍的数。 再比如5，其最小质因数为5，不超过5的质数有2,3和5，因此，遍历到5时就只会筛除 $5times2=10$，$5times3=15，$5times5$，而不去筛除35，55，65等更大的5的质数倍的数。

到这里我们理解了思想，到底要如何实现呢？再回头看看本节开篇的那段代码：

用最笨的方法来看，我们手写出算法的执行过程，试图从中找到规律：

当 $i=2$ 时，$prime[0]=2，pos=1$，此时进入内层 $for$ 循环： $j=0$ 时，会筛除掉 $i times prime[j]=2times2=4$，接下来判断 $i % prime[j]=2 % 2=0$，故跳出内层循环，从而本轮外循环也结束。

当 $i=3$ 时，$prime[1]=3，pos=2$，此时进入内层 $for$ 循环： $j=0$ 时，会筛除掉 $i times prime[j]=3times2=6$，接下来判断 $i % prime[j]=3 % 2 neq 0$，继续内层循环。 $j=1$ 时，会晒出掉 $i times prime[j]=3times3=9$，接下来判断 $i % prime[j]=3 % 3=0$，故跳出内层循环，从而本轮外循环也结束。

当 $i=4$ 时，已经被2筛除，非素数，此时直接进入内层 $for$ 循环： $j=0$ 时，会筛除掉 $i times prime[j]=4times2=8$，接下来判断 $i % prime[j]=4 % 2=0$，故跳出内层循环，从而本轮外循环也结束。

当 $i=5$ 时，$prime[2]=5，pos=3$，此时进入内层 $for$ 循环： $j=0$ 时，会筛除掉 $i times prime[j]=5times2=10$，接下来判断 $i % prime[j]=5 % 2 neq 0$，继续内层循环。 $j=1$ 时，会筛除掉 $i times prime[j]=5times3=15$，接下来判断 $i % prime[j]=5 % 3 neq 0$，继续内层循环。 $j=2$ 时，会筛除掉 $i times prime[j]=5times5=25$，接下来判断 $i % prime[j]=5 % 5=0$，故跳出内层循环，从而本轮外循环也结束。

从以上执行过程，不难发现：

当 $i$ 为素数时，会首先将自己添加到素数存储数组中 $prime$ 中，然后进入内层 $for$ 循环中筛除其倍数，直至 $i % prime[j]==0$，而 $i$ 是素数，仅有一个质因数，即其本身，也就是说当前遍历到的数为 $i$ 时，会筛除 $i$ 与全部不超过其最小质因数($i$ 本身)的素数之积； 当 $i$ 为非素数时，已经被前面的素数筛除掉，即不能将自己添加到素数存储数组 $prime$ 中，因此直接进入内层 $for$ 循环中筛选其倍数，直至 $i % prime[j]==0$，而 $i$ 是非素数，可能有多个质因数，而要满足该跳出循环的条件，$prime[j]$ 就是 $i$ 的最小质因数，从而会在内层循环中筛除 $i$ 与全部不超过其最小质因数($prime[j]_{min}$)的素数之积。

整合两种情况，得出以下结论：

每次遍历到一个数 $i$，无论素数与否，都会筛除数 $i$ 与其全部不超过其最小质因数的素数之积

还是不够直观是吧，那再看下面这张表：

第一列即筛除掉全部以2为最小质因数的数，第二列筛除掉全部以3为最小质因数的数…依次类推，可以把所有的合数都筛掉。

因为是按照最小素因子筛选，所以可以保证每个数都只会被筛一遍。

上面是我的通俗理解，下面援引自此篇，感觉分析得更为严谨，也放在这里供大家参考：

这段代码最难理解的是这句：

要理解这句话，（顺便不严谨地）证明这个算法的时间复杂度和正确性，要从以下两个方面： 每个数至少被访问一次 对于质数，一定会在 $i$ 的循环中访问到，并确定为质数。 对于合数，因为每一个合数都可以表示成它最小的质因数和另一个数的乘积，而我们枚举了所有的另一个数（也就是 $i$），所以它一定会被它的最小质因数筛掉。 每个数至多被访问一次 对于质数，不可能在 $j$ 的循环中被访问到，因此仅会在 $i$ 的循环中被访问到恰好一次。 对于合数，对于 $i = i_1 = p times a$，因为在 $i_1 % prime[j_1] == 0$ 时 $break$，所以不可能出现一个数 $x=i_1 times prime[k]=p times a times prime[k] (k > j_1)$ 在 $i = i_1, j = k$ 的时候被筛掉一次，又在 $i = a times prime[k]$ 的时候被 $p$ 给筛掉的情况。 综上所述，每个数被访问一次且仅访问一次！因此整个算法的复杂度是 $O(n)$ 的。

面试结果

hmmmmmmmm… 当然，很愉快的，即使是在面试官迟到了1小时的情况下，TT还是很给面子，没让我过，我记住了，哼！ 不过好事多磨，总有收获还是不错的啦～再接再厉！

参考资料

[1]菜鸟学线性筛素数 [2]欧拉筛法找素数 [3]求1000000以内的素数 [4]线性时间内筛素数和欧拉函数