埃拉托色尼筛法： 该算法用于查找（识别）列表中的素数。 提示： 从划掉较小素数的倍数开始

  • 希腊数学家 Eratosthenes （公元前275一前193）当时使用了一种新的简单方法来确定列表中的数字是否为素数。
  • 他从已知的小素数 2、3、5、7、11、13、17、23 等开始。很明显，它们的倍数都不是素数，而是合数。
  • 他按升序排列了一个自然数列表。 之后，他确定并删除了该列表中所有较大的合数，因为它们是较小素数的倍数。这样，经过几次迭代，他列表中的所有数字都只是素数。
  • 我们在下面说明此方法，并使用从 2 到 100 升序排列的数字列表：
  • 数字 2 是一个素数，所以我们首先确定列表中所有 2 的倍数：
  • 2 × 2 = 4
  • 2 × 3 = 6
  • 2 × 4 = 8
  • 2 × 5 = 10
  • 2 × 6 = 12
  • 2 × 7 = 14
  • 2 × 8 = 16
  • 2 × 9 = 18
  • 2 × 10 = 20
  • ... 等等，直到数字： 2 × 50 = 100.
  • 数字 2 × 51 = 102 大于 100，所以我们可以停下来。
  • 从列表中删除数字 2 的所有倍数： 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100.
  • 数字 3 是下一个素数，因此我们在列表中识别出所有 3 的倍数：
  • 3 × 2 = 6 （这个数字已经从列表中删除，它是 2 的倍数）；
  • 3 × 3 = 9
  • 3 × 4 = 12 （这个数字已经从列表中删除，它是 2 的倍数）；
  • 3 × 5 = 15
  • 3 × 6 = 18 （这个数字已经从列表中删除，它是 2 的倍数）；
  • ...等等，直到数字：3 × 33 = 99.
  • 数字 3 × 34 = 102 大于 100，所以我们可以停下来。
  • 从列表中删除数字 3 的所有倍数： 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 97, 99.
  • 如果我们已经从列表中删除了数字 2 的所有倍数，我们只剩下： 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93. 99. 这些数字写在下面，作为数字 3 的倍数：
  • 3 × 3 = 9
  • 3 × 5 = 15
  • 3 × 7 = 21
  • 3 × 9 = 3 × 3 × 3 = 27
  • 3 × 11 = 33
  • 3 × 13 = 39
  • 3 × 15 = 3 × 3 × 5 = 45
  • 3 × 17 = 51
  • 3 × 19 = 57
  • 3 × 21 = 3 × 3 × 7 = 63
  • 3 × 23 = 69
  • 3 × 25 = 3 × 5 × 5 = 75
  • 3 × 27 = 3 × 3 × 3 × 3 = 81
  • 3 × 29 = 87
  • 3 × 31 = 93
  • 3 × 33 = 3 × 3 × 11 = 99.
  • 然后我们继续下面的质数，5：
  • 5 × 2 = 10 （此数字已从列表中删除 - 它是 2 的倍数）；
  • 5 × 3 = 15 （此数字已从列表中删除 - 它是 3 的倍数）；
  • 5 × 4 = 20（此数字已从列表中删除 - 它是 2 的倍数）；
  • 5 × 5 = 25
  • 5 × 6 = 30 （此数字已从列表中删除 - 它是 2 和 3 的倍数）；
  • 5 × 7 = 35
  • ...依此类推，直到数字：5 × 20 = 100（此数字已从列表中删除 - 它是 2 的倍数）。
  • 数字 5 × 21 = 105 大于 100，所以我们可以停下来。
  • 从列表中删除数字 5 的所有倍数： 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100.
  • 如果我们已经从列表中删除了 2 和 3 的倍数，我们仍然需要删除这些数字： 25, 35, 55, 65, 85, 95, 正是那些在素因数分解中素因数大于或等于 5 的数字：
  • 5 × 5 = 25
  • 5 × 7 = 35
  • 5 × 11 = 55
  • 5 × 13 = 65
  • 5 × 17 = 85
  • 5 × 19 = 95.
  • 然后我们用下一个素数 7 重复这个过程：
  • 7 × 2 = 14 （该数字已从列表中删除 - 它是 2 的倍数）；
  • 7 × 3 = 21 （该数字已从列表中删除 - 它是 3 的倍数）；
  • 7 × 4 = 28 （该数字已从列表中删除 - 它是 2 的倍数）；
  • 7 × 5 = 35 （该数字已从列表中删除 - 它是 5 的倍数）；
  • 7 × 6 = 42 （该数字已从列表中删除 - 它是 2 和 3 的倍数）；
  • 7 × 7 = 49
  • ...等等，直到数字：7 × 14 = 98 （该数字已从列表中删除 - 它是 2 的倍数）；
  • 7 × 15 = 105，大于 100，所以我们可以停止。
  • 从列表中删除数字 7 的所有倍数： 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98.
  • 如果我们从列表中删除了数字 2、3 和 5 的所有倍数，我们仍然需要删除： 49, 77, 91. 这些正是在其素因数分解中具有大于或等于 7 的素因数的数字：
  • 7 × 7 = 49
  • 7 × 11 = 77
  • 7 × 13 = 91.
  • 列表中的下一个素数是 11，我们应该从列表中删除 11 的倍数。
  • 然而，正如我们在上面的步骤中看到的，我们应该尝试从列表中删除仅在其分解中具有大于或等于 11 的素因子的数字。
  • 但已经 11 × 11 = 121，大于 100。
  • 这意味着执行上述步骤后列表中剩余的所有数字已经只是素数。
  • 素数列表包含未删除的数字。
  • 从列表中删除所有素数 2、3、5 和 7 的倍数后，我们在列表中留下了这些数字： 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 - 素数列表 2 到 100。