算式

给出要筛数值的范围n，找出n{\displaystyle {\sqrt {n}}}以内的素数p1,p2,… … -->,pk{\displaystyle p_{1},p_{2},\dots ,p_{k}}。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个素数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。

步骤

详细列出算法如下：

列出2以后的所有序列：

标出序列中的第一个质数，也就是2，序列变成：

将剩下序列中，划摽2的倍数（用红色标出），序列变成：

如果现在这个序列中最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是质数，否则回到第二步。

本例中，因为25大于2的平方，我们返回第二步：

剩下的序列中第一个质数是3，将主序列中3的倍数划出（红色），主序列变成：

我们得到的质数有：2，3

25仍然大于3的平方，所以我们还要返回第二步：

现在序列中第一个质数是5，同样将序列中5的倍数划出，主序列成了：

我们得到的质数有：2 3 5 。

因为25等于5的平方，跳出循环.

结论：去掉红色的数字，2到25之间的质数是：2 3 5 7 11 13 17 19 23。

算法

埃拉托斯特尼筛法，可以用以下的伪代码来表示：

以上算法可以得到小于等于n的所有素数，它的复杂度是O(n log log n)。

程式代码

Python 3.6

deferatosthenes(n):P=[iforiinrange(2,n+1)]p=0whileTrue:foriinP[p+1:]:ifi%P[p]==0:P.remove(i)ifP[p]**2>=P[-1]:breakp+=1returnPif__name__=="__main__":print(eratosthenes(120))

C++

#include#include//std::remove_if#include//std::iotastd::vectoreratosthenes(intmax){std::vectorvi(max+1);//0, 1, 2, ..., maxstd::iota(vi.begin(),vi.end(),0);if(max>=2){intprime=2;while(prime*prime<=max){//2 to sqrt(max)for(size_tindex=prime*2;index<vi.size();index+=prime){vi[index]=0;//Rule out this number.}for(prime++;prime*prime0){break;//Jump to next non-zero.}}}}vi.erase(std::remove_if(vi.begin(),vi.end(),[](inti)->bool{returni<=1;}),vi.end());//Remove all zeros and the one.returnvi;}

计算分析

算法复杂度

参见

卢卡斯-莱默检验法

米勒-拉宾检验

试除法

费马素性检验

孪生素数

三胞胎素数

四胞胎素数

素数判定法则

表兄弟素数

六素数

X²+1素数

参考文献

Κοσκινον Ερατοσθενους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S., Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。