筛选法

C语言

先解释一下筛选法的步骤：

<1>先将1挖掉(因为1不是素数)。

<2>用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。

<3>用3去除它后面的各数，把3的倍数挖掉。

<4>分别用5…各数作为除数去除这些数以后的各数。

上述操作需要一个很大的容器去装载所有数的集合，只要满足上述条件，即2的倍数大于1的全部置0，3的倍数大于1的全部置0，4的倍数大于1的全部置0.。。。一直到这个数据集合的末尾，这样一来不为0的数就是素数了，然后按下标在里面进行查找就好了

求某项自然数A之内的素数

实现一

1.抽象步骤

<1>先将1去掉

<2>将2的倍数去掉。

<3>将3的倍数去掉。

……

将i的倍数去掉。

……

一直到A。

2.具体化

以数组array[n]为例，其中array[n]=n+1;

循环开始

<1>判断array的值。

array的值是1；不执行操作

<2>判断array的值。

array的值是2；

用array去除它后面的array、array、array……array[n]；

能被array整除的，例如array(值为4）、array(值为6），全部置1；

即：if(array[i]%array==0)array[i]=1;

i=2,3,4……n

<3>判断判断array的值。

array的值是3；

用array去除它后面的各数，把array的倍数全部置1。

比如array（值为9），array（值为15），全部置为"1"。

即：if(array[i]%array==0)array[i]=1;

i=3,4,5……n

<4>判断array的值。

array原本的值为4，但是经过步骤<2>，现array的值为1；

换句话说，如果array的值为1，那么它一定可以被array和array中的某一个整除。

所以array曾经是合数，不执行操作。

………………………

判断array[i]的值。

如果array[i]==1，那么array[i]一定可以被array、array、……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]的值。

如果array[n]==0，那么array[n]一定可以被array~array[n-1]中的一项整除。

所以array[n]是合数，不执行任何操作。

如果array[n]！=0，那么array~array[n-1]都不能将它整除。

所以array[n]是素数。

循环结束。

经过以上循环，所有合数都被置“1”，输出所有非“1”的array[]。

即if（array[i]！=1）printf("%d",array[i]);

程序结束。

3.代码实现

for(j=i+1;jj++)//执行操作:用array[i]除后面的array[i+1]~array[n]

{

if(array[j]%array[i]==0)//能被array[i]整除的即为合数。

array[j]=1;//合数都被重置为"1"。

实现二

此筛选法遵循了C程序模块化的习惯，将筛选法独立为一个函数在主函数里调用，此代码在VC6.0中完全可以直接使用。

参考资料

筛选实现C++实现筛选法·开发者知识库