【原】埃拉托色尼筛选法，找出所有小于给定正整数n的质数

在数学中，埃拉托色尼筛选法（the Sieve of Eratosthenes）是一种古老的算法，用来找出不超过任何给定整数n的所有质数。

它通过迭代地将每个质数的倍数标记为合数，从第一个质数2开始。一个给定质数的倍数组成一个以这个质数开头的等差数列，差就是这个质数。一旦所有发现的质数的倍数都被标记为合数，其余未标记的数就是质数。用埃拉托色尼筛法找到所有小于或等于给定整数n的质数：

1. 建立一个从2到n的连续整数列表：(2, 3, 4, ……, n)。
2. 最初，让p等于2，即最小的素数。
3. 通过从2p到n的增量来列举p的倍数，并在列表中标记它们（这些将是2p，3p，4p，……；p本身不应该被标记）。
4. 找出列表中大于p的最小的数字，该数字未被标记。如果没有这样的数字，就停止。否则，让p现在等于这个新的数字（这是下一个素数），然后从第3步开始重复。

当算法结束时，列表中剩下的未标记的数字是所有小于n的素数。

• 121以下质数的算法步骤
  

这里的主要思想是，p的每一个值都是素数，因为如果它是合数，它将被标记为其他一些更小的素数的倍数。请注意，有些数字可能会被标记不止一次（例如，15将被标记为3和5）。

作为一种改进，在步骤3中从p^2开始标记数字就足够了，因为所有p的小倍数在这时已经被标记。这意味着，当p^2大于n时，算法可以在第4步终止。

举例

要找到所有小于或等于30的质数，按以下步骤进行。首先，生成一个从2到30的整数列表：

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

列表中的第一个数字是2，从2开始以2为单位递增，划掉列表中2之后的第2个数字（这些将是列表中所有2的倍数）：

2之后的数字是3，从3开始，划掉列表中3之后所有3的倍数的数字：

在3之后，下一个没有被划掉的数字是5，从5开始，划掉列表中5之后所有是5的倍数的数字：

下一个在5之后还没有划掉的数字是7，下一步是划掉7之后所有是7倍数的数字，但它们都已经划掉了，因为这些数字（14,21,28）也是较小质数的倍数，因为7 × 7大于30。此时，列表中未划掉的数字是所有低于30的质数：