篩選法
篩選法
篩選法又稱篩法，具體做法是：先把N個自然數按次序排列起來。1不是質數，也不是合數，要劃去。第二個數2是質數留下來，而把2後面所有能被2整除的數都劃去。2後面第一個沒劃去的數是3，把3留下，再把3後面所有能被3整除的數都劃去。3後面第一個沒劃去的數是5，把5留下，再把5後面所有能被5整除的數都劃去。這樣一直做下去，就會把不超過N的全部合數都篩掉，留下的就是不超過N的全部質數。因為希臘人是把數寫在塗臘的板上，每要劃去一個數，就在上面記以小點，尋求質數的工作完畢后，這許多小點就像一個篩子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼篩”，簡稱“篩法”。（另一種解釋是當時的數寫在紙草上，每要劃去一個數，就把這個數挖去，尋求質數的工作完畢后，這許多小洞就像一個篩子。）
先解釋一下篩選法的步驟：
<1> 先將1挖掉(因為1不是素數)。
<2> 用2去除它後面的各個數，把能被2整除的數挖掉，即把2的倍數挖掉。
<3> 用3去除它後面的各數，把3的倍數挖掉。
<4> 分別用5…各數作為除數去除這些數以後的各數。
上述操作需要一個很大的容器去裝載所有數的集合，只要滿足上述條件，即2的倍數大於1的全部置0，3的倍數大於1的全部置0，4的倍數大於1的全部置0……一直到這個數據集合的末尾，這樣一來不為0的數就是素數了，然後按下標在裡面進行查找就好了
1.抽象步驟
<1>先將1去掉
<2>將2的倍數去掉。
<3>將3的倍數去掉。
……
將i的倍數去掉。
……
一直到A。
2.具體化
以數組array[n]為例，其中array[n]=n+1;
循環開始
<1> 判斷array[0]的值。
array[0]的值是1；不執行操作
<2> 判斷array[1]的值。
array[1]的值是2；
用array[1]去除它後面的array[2]、array[3]、array[4]……array[n]；
能被array[1]整除的，例如array[3](值為4）、array[5](值為6），全部置1；
即：if (array[i]%array[1]==0) array[i]=1;
i=2,3,4……n
<3> 判斷判斷array[2]的值。
array[2]的值是3；
用array[2]去除它後面的各數，把array[2]的倍數全部置1。
比如array[8]（值為9），array[14]（值為15），全部置為"1"。
即：if (array[i]%array[2]==0) array[i]=1;
i=3,4,5……n
<4> 判斷array[3]的值。
array[3]原本的值為4，但是經過步驟<2>，現array[3]的值為1；
換句話說，如果array[3]的值為1，那麼它一定可以被 array[2] 和 array[3] 中的某一個整除。
所以array[3]曾經是合數，不執行操作。
………………………
判斷array[i]的值。
如果 array[i]==1，那麼array[i]一定可以被array[2]、array[3]、……array[i-1]中的某一個數整除
所以曾經的array[i]是合數，不執行任何操作。
否則 array[i]!=1，那麼array[i]是素數。
用array[i]去除array[i+1]、array[i+2]、……array[n]。
能被array[i]整除的各項，全部置1。
………………………
如果 array[n]==1，那麼array[n]一定可以被array[2]~array[n-1]中的一項整除。
所以array[n]是合數，不執行任何操作。
如果 array[n]！=1，那麼array[2]~array[n-1]都不能將它整除。
所以 array[n]是素數。
循環結束。
經過以上循環，所有合數都被置“1”，輸出所有非“1”的array[]。
即if（array[i]！=1） printf("%d",array[i]);
程序結束。
3.代碼實現
此篩選法遵循了C程序模塊化的習慣，將篩選法獨立為一個函數在主函數里調用，此代碼在VC6.0中完全可以直接使用。
