一、簡介
埃拉托斯特尼篩法，簡稱埃氏篩或愛氏篩，是一種由埃及數學家埃拉托斯特尼所提出的一種簡單檢定素數的算法。要得到自然數n以內的全部素數，必須把不大於√n的所有素數的倍數剔除，剩下的就是素數
二、步驟
我們詳細列出算法如下：
第一步，列出如下這樣以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 5 7 9 11 13 15 17 19 21 23 25
第四步，如果現在這個序列中最大數小於第一個素數的平方，那么剩下的序列中所有的數都是素數，否則返回第二步。
本例中，因為25大於2的平方，我們返回第二步：
剩下的序列中第一個素數是3，將主序列中3的倍數劃出（紅色），主序列變成：
3 5 7 11 13 15 17 19 23 25
我們得到的素數有：2，3。
25仍然大於3的平方，所以我們還要返回第二步：
現在序列中第一個素數是5，同樣將序列中5的倍數劃出，主序列成了：
5 7 11 13 15 17 19 23 25
我們得到的素數有：2 3 5 。
因為25等於5的平方，跳出循環.
結論：去掉紅色的數字，2到25之間的素數是：2 3 5 7 11 13 17 19 23。
篩選的主要方法
1.划去2的倍數；
2.划去3的倍數；
3 划去5的倍數；（4的倍數同為2的倍數，已被划去）
4.划去7的倍數；（6的倍數同為3的倍數，已被划去）
5.划去11的倍數；（8和10的倍數同為2的倍數，而9的倍數也是3的倍數）
所以驗證一個數是否是素數，可以用它來除以2，3，5，7，11。
一個篩子，專門篩掉合數，保留素數。）
兩個相等區間同樣篩法的差異
如果兩個或者兩個以上的相等區間，使用同樣篩法，會出現情況就是：任何兩個相等區間篩k次以後，相差不會超過k個。
相等區間篩法1
相等區間篩法2