愛氏篩與質數

埃拉托斯特尼篩法，簡稱埃氏篩或愛氏篩，是一種由埃及數學家埃拉托斯特尼所提出的一種簡單檢定質數的演算法。

[編輯] 步驟
我們詳細列出演算法如下：
第一步，列出如下這樣以2開頭的序列：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
第二步，標出序列中的第一個質數，主序列變成：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
第三步，將剩下序列中，第二項開始每隔一項劃掉(2的倍數,用紅色標出。），主序列變成：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
第四步，如果現在這個序列中最大數小於第一個質數的平方，那麼剩下的序列中所有的數都是質數，否則返回第二步。
本例中，因為25大於2的平方，我們返回第二步：

剩下的序列中第一個質數是3，將主序列中3的倍數劃出（紅色），主序列變成：

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

我們得到的質數有：2，3。

25仍然大於3的平方，所以我們還要返回第二步：

現在序列中第一個質數是5，同樣將序列中5的倍數劃出，主序列成了：

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

我們得到的質數有：2 3 5 。

因為25等於5的平方，跳出循環.
結論：去掉紅色的數字，2到25之間的質數是：2 3 5 7 11 13 17 19 23。
素數，又稱質數，一個大於1的自然數中，除了1和此整數自身外，沒法被其他自然數整除的數；即是只有兩個正因數（1和自己）的自然數。
比1大但不是質數的數稱之為合數又稱合成數，而1和0既非質數也非合數。質數的屬性稱為素性，質數在數論中有著非常重要的地位。