C语言筛选法判断质数

楼上的别在那误导人，你那叫筛选法吗？

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

<1>

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

<2>

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

<3>

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

<4>

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

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

筛选法程序如下

#include<stdio.h>

int

main()

{

int

x[100001]

int

temp,n,

i

//初始化数组

for(i=0i<100001i++)

x[i]=0

//初始化数组完成

/*

预计结果，

数组中质数为0，其它为1

*/

x[0]=x[1]=1//因为

0和1不能通过计算得到，所以只能手工置1

，1即不是合数也不是质数

for(i=2i<100001i++)

{//循环数组中的每个数

if(x[i]==0){//如果该数所存的值为0，即第一次接触此数

temp=2*i//将它的二倍，及n倍（要小于100000）

，都置为1，因为这些数都能被i整除

while(temp<=100000)

{

x[temp]=1

temp+=i

}

}

}

scanf("%d",&n)

while(n

!=

0)

{

if(x[n]==0)

printf("素数\n")

else

printf("合数\n")

scanf("%d",&n)

}

return

0

}

如果你觉得这个方法不好理解，你可以用上面他们写的那些常规算法，但是数字过大的话，算起来是很慢的

以下为普通的筛质数法的程序： #include #include const int N=101int a[N],b[N]int main(void) { int i,ja[0]=a[1]=1for(i=2i=2j--)a[j*i]=1} for(i=1i

int x = 100//x为任意输入的数字

boolean isPrime = false

for(int i=2i<=x/2i++){

if(x % i == 0){

isPrime = true

break

}

}

if(isPrime){

System.out.println(x + "是质数")

}else{

System.out.println(x + "不是质数")

}

---