埃拉托斯特尼筛法
维基百科，自由的百科全书
埃拉托斯特尼筛法，簡稱埃氏篩或愛氏篩，是一種由埃及数学家埃拉托斯特尼所提出的一種簡單檢定素数的算法。
[编辑] 步驟
我们详细列出算法如下：
第一步，列出如下这样以2开头的序列：
- 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
第二步，标出序列中的第一个素数，主序列变成：
- 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
第三步，将剩下序列中，第二项开始每隔一项划掉(2的倍数,用红色标出。），主序列变成：
- 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
第四步，如果现在这个序列中最大数小于第一个素数的平方，那么剩下的序列中所有的数都是素数，否则返回第二步。
本例中，因为25大于2的平方，我们返回第二步：
- 剩下的序列中第一个素数是3，将主序列中3的倍数划出（红色），主序列变成：
- 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
- 我们得到的素数有：2，3。
- 25仍然大于3的平方，所以我们还要返回第二步：
- 现在序列中第一个素数是5，同样将序列中5的倍数划出，主序列成了：
- 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
- 我们得到的素数有：2 3 5 。
- 因为25等于5的平方，跳出循环.
结论：去掉红色的数字，2到25之间的素数是：2 3 5 7 11 13 17 19 23。
[编辑] 参考
Κοσκινον Ερατοσθενους 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.
