c語言中質數的判斷,質數判斷C語言

本文目錄一覽：

• 1、C語言判斷一個數是否是質數
• 2、c語言怎麼判斷一個數是素數
• 3、c語言判斷質數
• 4、C語言編程：判斷某數是否是質數
• 5、c語言判斷一個數是否為質數

C語言判斷一個數是否是質數

根據質數的定義，在判斷一個數n是否是質數時，只要用1至n-1去除n，看看能否整除即可。

還有更好的辦法：先找一個數m，使m的平方大於n，再用小於等於m的質數去除n（n為被除數），如果都不能整除，則n必然是質數。如我們要判斷1993是不是質數，50*501993，那麼只要用1993除以50的質數看是否能整除，若不能即為質數。100以內的質數有25個，還是比較好記的，只要記熟100以內質數，就可以快速判斷10000以內的數是不是質數。

100以內的質數有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97，在100內共有25個質數。

只有1和它本身兩個因數的自然數，叫質數（或稱素數）。（如：由2÷1=2，2÷2=1，可知2的因數只有1和它本身2這兩個約數，所以2就是質數。與之相對立的是合數：「除了1和它本身兩個因數外，還有其它因數的數，叫合數。」如：4÷1=4，4÷2=2，4÷4=1，很顯然，4的因數除了1和它本身4這兩個因數以外，還有因數2，所以4是合數。）

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

判斷是否是質數最直觀和簡單的方法就是從2開始直接除，能除盡（餘數為0）就不是質數。則C語言實現為：

int isprime(int m)

{

int i;

for(i=2;im;i++)

if(m%i==0）

return 0;

else

return 1;

}

該演算法的時間複雜度O(n)。

可以改進一下，根據如果一個數是合數，那麼它的最小質因數肯定小於等於它的平方根。用反證法可以證明一下。假設x是n的最小質因數，則存在n/x=p。px,x*p=n。如果x不小於等於它的平方根，則x*xn,而px，故x*pn,假設不成立。合數是與質數相對應的自然數。一個大於1的自然數如果它不是合數，則它是質數。也就是說如果一個數能被它的最小質因數整除的話，那它肯定是合數，即不是質數。所以判斷一個數是否是質數，只需判斷它是否能被小於它開跟號後的所有數整除，因此，這樣做的運算少了很多，降低了時間複雜度。

c語言判斷質數

#includestdio.h

#include math.h

void main()

{ int zhi(int);

int j=0,b[20]={1,3,7,9},a[20]={2,3,5,7},c,l=4,d[20],n,g=0,h=0,i,N,s=10,z,f;

scanf(“%d”,N);

for(i=1;i=N-1;i++)

{

for(j=0;jl;j++)

{

n=a[j]*s;

f=n;

for(h=0;h4;h++)

{ n=n+b[h];

c=zhi(n);

if(c==1)

d[++g]=n;

n=f;

}

}

for(j=0;jg;j++)

a[j]=d[j+1];

l=g,z=g,g=0;

}

if(N==1)

printf(“2\n3\n5\n7\n”);

else

for(j=1;j=z;j++)

printf(“%d\n”,d[j]);

}

int zhi(int m)

{ int k,i,c=0;

k=(int)sqrt(m);

for(i=2;i=k;i++)

if(m%i==0)break;

if(ik) c=1;

return c;

}

C語言編程：判斷某數是否是質數

#includestdio.h

int main(int argc,int argv[]){

int a，flag;

scanf(“%d”,a);/*輸入一個數進行判斷是否是質數*/

int isprime(int);/*這裡是對將要調用的函數聲明一下*/

flag=isprime(int);

if(flag==1) printf(“%d is isprime”,a);

printf(“%d is not isprime”,a):

return 1;/*這裡的語句代表調用函數成功*/

}

int isprime(int a){ /*功能函數，判斷是否是素數*/

int i;

for(i=2;i=a/2;i++)

if(a%i==0) return 0;/*只要有一次相除為0，馬上就能判斷不是素數*/

return 1;/*否則經過循環之後，都沒有相除為0呢，就說明一定是素數了*/

}

看到這裡是不是有點疑惑了呢？我到百度查了一下，質數也稱素數，你注意看就好。。不懂再追問。。

不過我想你看完之後你應該能明的了，我已經寫得好詳細了啦。。。。

c語言判斷一個數是否為質數

#includestdio.h

int main()

{

int i, n;

while (scanf(“%d”, n) != EOF)

{

for (i = 2; i n; i++)

if (n % i == 0)

break;

if (i = nn1)

printf(“%d是質數\n”, n);

else

printf(“%d不是質數\n”, n);

}

return 0;

}