更新时间：2024-05-21 11:09
筛选法又称筛法，具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。
埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。因为希腊人是把数写在涂蜡的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。（另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。）
要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。
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。
即：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[ ]
程序结束。
3.代码实现
此筛选法遵循了C程序模块化的习惯，将筛选法独立为一个函数在主函数里调用，此代码在VC6.0中完全可以直接使用。