这是一位大佬
就像上面这位朋友所说，求素数的方法确实有很多：100以下随便做，枚举估验特判开心就好，100000以下用6倍筛，1000000以下用埃氏筛，100万以上直接欧拉筛，不优化40000000以内秒过，一个亿以内的欧拉优化过……
我真被这简洁明了的概括惊呆了。
那今天就按照这样的顺序讲一下这些求素数的方法吧。
什么意思，就是最简单的定义来就好了。根据定义，判断一个整数n是否是素数，只需要去判断在整数区间[2,n-1]之内，是否具有某个数m，使得n%m==0。
我们把这种方法叫做朴素判断素数算法或者试除法，代码是这样的：
事实上，这个算法是O(n)的，感觉是很快了，但是依旧无法满足需求。
所以有一个算法是O(sqrt(n))的算法：
原理很巧妙，也仅仅是把代码的in变成了i*i=n而已，但是优化却是极其高的。可能你会注意到，在上一份代码里面，我定义的n为int类型，而后面一份代码，我却定义成了longlong，这是因为在1s内，上一份代码能判断出来的数量级为1e8，而后面一份代码判断出来的数量级却几乎可以达到1e16。而原因仅仅是因为a*b=c的话一旦a是c的约数，那么b也是，如果a不是，那么b也不是。
这里要插播一条诚挚的感谢，昨天的文章里出现了一个巨大的错误，被一个小可爱指出来了，如下：
确实我昨天的代码错了
犯这样的错误让我心痛不已！！！
以后一定痛定思痛，好好学习天天向上！
个人觉得这个方法，是一个神奇的发现。
来看一个关于质数分布的规律：大于等于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)，代码可以这么写：
这个算法可以说是黑科技级别的，它能够在3s内求出1e11之内的素数个数，据说还有在300ms内求出1e11的个数的。
本菜鸟我，望而却步啊，完全没有研究过，所以原理和代码大家就自行百度吧。
版权声明：本站所有作品（图文、音视频）均由用户自行上传分享，仅供网友学习交流，不声明或保证其内容的正确性，如发现本站有涉嫌抄袭侵权/违法违规的内容。请举报，一经查实，本站将立刻删除。