埃拉托色尼筛法: 该算法用于查找(识别)列表中的素数。 提示: 从划掉较小素数的倍数开始
- 希腊数学家 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。