埃拉托斯特尼筛法_埃拉托斯特尼筛法

埃拉托斯特尼筛法

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

算式

要得到自然数n以内的全部素数，必须把不大于的所有素数的倍数剔除，剩下的就是素数。

给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。

步骤

详细列出算法如下：

结论：2到25之间的素数是：2 3 5 7 11 13 17 19 23。

Pascal实现

c++实现

Java实现

python实现

ES6实现

参见

参考资料

最新修订时间：2023-12-01 10:21

条目作者

概述

算式

步骤

参考资料