埃拉托斯特尼筛法(埃拉托斯特尼筛法)

埃拉托斯特尼筛法

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

计算公式

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

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

计算步骤

详细列出算法如下：

列出2以后的所有序列：

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

算法实现

实现

资料参见

• 卢卡斯-莱默检验法

• 米勒-拉宾检验

• 试除法

• 费马素性检验

• 孪生素数

• 三胞胎素数

• 四胞胎素数

• 素数判定法则

• 表兄弟素数

• 六素数

• 素数

参考资料

Warning: Invalid argument supplied for foreach() in /www/wwwroot/newbaike1.com/id.php on line 362

条目作者

概述

计算公式

计算步骤

算法实现

资料参见

参考资料