c語言判斷質數

Ⅰ 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=0;i<100001;i++)
x[i]=0;
//初始化數組完成
/*
預計結果，
數組中質數為0，其它為1
*/
x[0]=x[1]=1;//因為
0和1不能通過計算得到，所以只能手工置1
，1即不是合數也不是質數
for(i=2;i<100001;i++)
{//循環數組中的每個數
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;
}
如果你覺得這個方法不好理解，你可以用上面他們寫的那些常規演算法，但是數字過大的話，算起來是很慢的

Ⅱ c語言怎麼判斷一個數是素數

判斷是否是質數最直觀和簡單的方法就是從2開始直接除，能除盡（余數為0）就不是質數。則C語言實現為：
int isprime(int m)
{
int i;
for(i=2;i<m;i++)
if(m%i==0）
return 0;
else
return 1;
}
該演算法的時間復雜度O(n)。
可以改進一下，根據如果一個數是合數，那麼它的最小質因數肯定小於等於它的平方根。用反證法可以證明一下。假設x是n的最小質因數，則存在n/x=p。p>x,x*p=n。如果x不小於等於它的平方根，則x*x>n,而p>x，故x*p>n,假設不成立。合數是與質數相對應的自然數。一個大於1的自然數如果它不是合數，則它是質數。也就是說如果一個數能被它的最小質因數整除的話，那它肯定是合數，即不是質數。所以判斷一個數是否是質數，只需判斷它是否能被小於它開跟號後的所有數整除，因此，這樣做的運算少了很多，降低了時間復雜度。