离散数学/埃拉托斯特尼筛法

交互式 SVG：单击缩略图，然后单击按钮清除表格或突出显示相应的倍数

埃拉托斯特尼筛法是一种查找素数的方法，它被认为是古希腊数学家埃拉托斯特尼发明的。这个想法是，首先列出所有大于 2 的自然数。

$2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24\ldots$

然后从 2 开始，我们找到第一个未划掉的数字，并划掉列表中该数字的所有倍数。

所以在 2 的情况下，没有数字被划掉，所以我们从 2 开始，划掉每个偶数。我们的列表将变为

$1,2,3,{\cancel {4}},5,{\cancel {6}},7,{\cancel {8}},9,{\cancel {10}},11,{\cancel {12}},13,{\cancel {14}},15,{\cancel {16}},17,{\cancel {18}},19,{\cancel {20}},21,{\cancel {22}},23,{\cancel {24}}\ldots$

我们不断应用我们的规则。下一个未划掉的数字是 3，我们划掉 3 之后的每个第三个数字。这将是 6、9、12、…，我们的列表变为

$1,2,3,{\cancel {4}},5,{\cancel {6}},7,{\cancel {8}},{\cancel {9}},{\cancel {10}},11,{\cancel {12}},13,{\cancel {14}},{\cancel {15}},{\cancel {16}},17,{\cancel {18}},19,{\cancel {20}},{\cancel {21}},{\cancel {22}},23,{\cancel {24}}\ldots$

等等。最后，只有素数会留下。

在这种情况下，我们已经找到了所有小于 25 的素数。这是因为合数必须始终有一个小于其平方根的素因子。如果对于某个整数 $n$ 不是这样，我们可以写成 $n=p_{1}\times p_{2}\times \cdots \times p_{k}$。由于我们假设 $n$ 是合数，我们知道至少有两个素因子 $p_{1}$ 和 $p_{2}$。如果它们都大于 ${\sqrt {n}}$，则 $p_{1}\times p_{2}>{\sqrt {n}}\times {\sqrt {n}}=n$。这将与 $n=p_{1}\times p_{2}\times \cdots \times p_{k}$ 相矛盾。因此，对我们来说，由于我们已经划掉了每个小于 5 的因子的数字，我们已经划掉了所有小于 $5^{2}=25$ 的合数。