使用者:Corindo/埃拉托斯特尼篩法
埃拉托斯特尼篩法，簡稱埃氏篩，是一種用來尋找小於等於某個限定數值的所有素數，生成素數表的方法。它的思想是從2開始依次找出是其餘數字若干倍的數（這些數都是合數）並刪去，直到只剩下不是其餘數若干倍的數，而這些數就是所有的素數。它得名於古希臘數學家、天文學家埃拉托斯特尼。埃拉托斯特尼關於篩法的作品文獻已經佚失。最早提到埃拉托斯特尼的篩法的文字是古羅馬數學家尼克馬諸斯寫於公元前一世紀的著作《數論導引》（Introduction to Arithmetic）。
方法 編輯
首先定義素數：素數是只能被1與它自身整除的自然數。埃拉托斯特尼篩法的目標是找出小於等於給定自然數N的所有素數。具體步驟是：
- 將從2到N的所有自然數排成一列：L = 2,3, ... ,N
- 找出L中沒有被標記為素數也沒有被劃掉的數裡面最小的一個：p（一開始來說，這個數是2），將p標記為素數。
- 將L中所有p的倍數（p自己除外）：2p、3p等等都劃掉。
- 重複以上兩步，直到L中所有的數都被標記或者被劃掉。這時沒被劃掉的就是小於等於N的所有素數。
埃拉托斯特尼篩法的根據是：如果某個數p前面的數都被標記為素數或者被劃掉了，而它還沒被劃掉，說明它不是2到p - 1中的任何數的倍數，即2到p - 1中沒有一個數整除p。如果p是素數，那麼在劃掉2到p - 1的倍數時，p不會被劃掉。所以當2到p - 1都被劃掉以後，p成為了沒被劃掉的數裡面最小的一個，從而它會被加入到素數表里去。合數必然會在劃掉它的某個因子的所有倍數時被劃掉，從而無法等到成為沒被標記或沒被劃掉的數裡面最小數的那個時刻。
為了提高效率，可以對埃拉托斯特尼篩法進行改良。注意到當我們開始劃掉L中所有p的倍數時，我們實際上是從p2開始的。因為當k小於p時，kp也是k的倍數，所以在劃掉k的倍數以後，kp肯定也被劃掉了。所以篩法中劃倍數的步驟可以改為：將L中所有p的倍數里大於等於p2的那些劃掉。這也說明，當p2大於N時，篩法實際上就結束了，只需將剩餘沒有被劃掉的數全部標記為素數即可。
無限定範圍的篩法 編輯
埃拉托斯特尼篩法的目標是找出限定範圍內的素數。稍作修改後，篩法可以用來生成素數序列，而不需要限定範圍。
試除法 編輯
有時候，人們會將埃拉托斯特尼篩法與逐個試除法混淆起來。試除法是一種較為低效的尋找素數方法。給定限定範圍N，試除法指對每個小於等於N的自然數n，用2到n-1來除n，驗證n是否是素數。
例子 編輯
以下用埃拉托斯特尼篩法尋找小於等於30的所有素數。
首先將從2到30的所有數排成一列：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
裡面最小的數是2。把2標記為素數，然後把所有2的倍數劃掉：
2 3456789101112131415161718192021222324252627282930
比2大而還沒被劃掉的數裡面最小的是3. 將3標記為素數，然後把所有3的倍數劃掉：
2 3456789101112131415161718192021222324252627282930
比3大而還沒被劃掉的數裡面最小的是5. 將5標記為素數，然後把所有5的倍數劃掉：
2 3456789101112131415161718192021222324252627282930
比5大而還沒被劃掉的數裡面最小的是7. 將7標記為素數，然後把7劃掉，再把所有7的倍數劃掉。然而這時候可以看到，所有7的倍數：(14, 21, 28)已經被劃掉了。如果繼續篩法，可以發現，之後的步驟都只有標記素數，而沒有新的數被劃掉了。最後剩下的數是：
2 3 5 7 11 13 17 19 23 29
如果使用改良的篩法，則步驟如下：
一開始把2標記為素數，然後從4開始把所有2的倍數劃掉：
2 3456789101112131415161718192021222324252627282930
比2大而還沒被劃掉的數裡面最小的是3. 將3標記為素數，然後從9開始，把所有3的倍數劃掉：
2 3456789101112131415161718192021222324252627282930
比3大而還沒被劃掉的數裡面最小的是5. 將5標記為素數，然後從25開始把所有5的倍數劃掉：
2 3456789101112131415161718192021222324252627282930
比5大而還沒被劃掉的數裡面最小的是7. 而7的平方已經大於30了。所以這時候可以停止篩法，這時剩餘的數就是30以內所有的素數。
可以看到，兩次篩法在任何時刻的狀態都是一樣的，但後者省去了重複劃掉倍數的過程。