離散數學/埃拉託斯特尼篩法

互動式 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$ 的合數。