昨天发出C语言经典算法（二）｜1-100之间有多少个素数之后，收到很多朋友的评论，讨论更高效的求素数的方法，我将大家的评论一一看过，觉得受益良多，同时也没有闲着，动手又敲了一遍这些精妙的求素数的方法，发出来与大家共享。

这是一位大佬

就像上面这位朋友所说，求素数的方法确实有很多：100以下随便做，枚举估验特判开心就好，100000以下用6倍筛，1000000以下用埃氏筛，100万以上直接欧拉筛，不优化40000000以内秒过，一个亿以内的欧拉优化过……

我真被这简洁明了的概括惊呆了。

那今天就按照这样的顺序讲一下这些求素数的方法吧。

100以内：随便做

什么意思，就是最简单的定义来就好了。根据定义，判断一个整数n是否是素数，只需要去判断在整数区间[2, n-1]之内，是否具有某个数m，使得n % m == 0。

我们把这种方法叫做朴素判断素数算法或者试除法，代码是这样的：

事实上，这个算法是O(n)的，感觉是很快了，但是依旧无法满足需求。

所以有一个算法是O(sqrt(n))的算法：

原理很巧妙，也仅仅是把代码的i < n变成了i * i <= n而已，但是优化却是极其高的。可能你会注意到，在上一份代码里面，我定义的n为int类型，而后面一份代码，我却定义成了long long，这是因为在1s内，上一份代码能判断出来的数量级为1e8，而后面一份代码判断出来的数量级却几乎可以达到1e16。而原因仅仅是因为a * b = c的话一旦a是c的约数，那么b也是，如果a不是，那么b也不是。

这里要插播一条诚挚的感谢，昨天的文章里出现了一个巨大的错误，被一个小可爱指出来了，如下：

确实我昨天的代码错了

犯这样的错误让我心痛不已！！！

以后一定痛定思痛，好好学习天天向上！

6倍筛：一个神奇的规律

个人觉得这个方法，是一个神奇的发现。

来看一个关于质数分布的规律：大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等。

这个规律的正确性我们这里就不证明了，大家有兴趣可以去查查资料，或者等待大佬评论区解答。

好，那么知道这个规律，此时判断质数就可以6个为单元快进，即将前面的方法循环中i++步长加大为6，加快判断速度，原因是，假如要判定的数为n，则n必定是6x-1或6x+1的形式，对于循环中6i-1，6i，6i+1,6i+2，6i+3，6i+4，其中如果n能被6i，6i+2，6i+4整除，则n至少得是一个偶数，但是6x-1或6x+1的形式明显是一个奇数，故不成立；另外，如果n能被6i+3整除，则n至少能被3整除，但是6x能被3整除，故6x-1或6x+1（即n）不可能被3整除，故不成立。

综上，循环中只需要考虑6i-1和6i+1的情况，即循环的步长可以定为6，每次判断循环变量k和k+2的情况即可，理论上讲这种方法整体速度应该会是朴素判断素数法的3倍。代码如下：

埃氏筛选法（埃拉托斯特尼筛法）

埃氏筛选法对于筛选整数n以内的素数，算法是这么描述的：先把素数2的倍数全部删除，剩下的数第一个为3，再把素数3的倍数全部删除，剩下的第一个数为5，再把素数5的倍数全部删除······直到把n以内最后一个素数的倍数删除完毕，得到n以内的所有素数。代码可以这么写：

这就是下面这位小可爱的观点：

线性筛选

观察可以发现，上面的这种写法有很多次重复计算，这样显然无法做到线性筛选，而另外一种写法却可以得到线性筛选，达到时间复杂度为O(n)，代码可以这么写：

Meissel-Lehmer算法

这个算法可以说是黑科技级别的，它能够在3s内求出1e11之内的素数个数，据说还有在300ms内求出1e11的个数的。

本菜鸟我，望而却步啊，完全没有研究过，所以原理和代码大家就自行百度吧。