您好,登錄后才能下訂單哦!
本文小編為大家詳細(xì)介紹“怎么用C語言判斷一個(gè)數(shù)是否為素?cái)?shù)”,內(nèi)容詳細(xì),步驟清晰,細(xì)節(jié)處理妥當(dāng),希望這篇“怎么用C語言判斷一個(gè)數(shù)是否為素?cái)?shù)”文章能幫助大家解決疑惑,下面跟著小編的思路慢慢深入,一起來學(xué)習(xí)新知識(shí)吧。
一、概念介紹
素?cái)?shù)又稱為質(zhì)數(shù)。一個(gè)大于1的自然數(shù)(從2開始),除了1和它本身外,不能被其他自然數(shù)整除的叫做素?cái)?shù),否則稱為合數(shù)。
0和1既不是素?cái)?shù)也不是合數(shù),最小的素?cái)?shù)是2。
二、代碼
方法一:
bool is_Prime(int num){
int i;
for(i = 2;i <= sqrt(num);i++){
if(num % i == 0)//一旦發(fā)現(xiàn)有因子,則返回false
return false;
}
return true;
}
注意:在for循環(huán)判斷時(shí)不能忘記 i <= sqrt(num) 的等號(hào),因?yàn)榧僭O(shè) p*p = n , n的因子是可以取到 sqrt(n) 的,如判斷 9 是不是素?cái)?shù),如果沒有等號(hào)會(huì)出現(xiàn) 9是素?cái)?shù),而實(shí)際上 9不是素?cái)?shù)。
方法二:
關(guān)于質(zhì)數(shù)分布的規(guī)律:大于等于5的質(zhì)數(shù)一定和6的倍數(shù)相鄰。例如5和7,11和13,17和19等等;
證明:令x≥1,將大于等于5的自然數(shù)表示如下:
··· 6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5,6(x+1),6(x+1)+1 ···
可以看到,不和6的倍數(shù)相鄰的數(shù)為6x+2,6x+3,6x+4,由于2(3x+1),3(2x+1),2(3x+2),所以它們一定不是素?cái)?shù),再除去6x本身,顯然,素?cái)?shù)要出現(xiàn)只可能出現(xiàn)在6x的相鄰兩側(cè)。因此在5到sqrt(n)中每6個(gè)數(shù)只判斷2個(gè),時(shí)間復(fù)雜度O(sqrt(n)/3)。
在高配版和尊享版中,都是一個(gè)剪枝的思想,高配版中裁剪了不必要的偶數(shù),尊享版中裁剪了不和6的倍數(shù)相鄰的數(shù),雖然都沒有降低時(shí)間復(fù)雜度的階數(shù),但都一定程度上加快了判斷的速度。
/*一種高效的方法*/
bool isPrime_3(int num){
//兩個(gè)較小數(shù)另外處理
if(num == 2 || num == 3)
return true;
//不在6的倍數(shù)兩側(cè)的一定不是質(zhì)數(shù)
if(num % 6 != 1 && num % 6 != 5)
return false;
int i;
//在6的倍數(shù)兩側(cè)的也可能不是質(zhì)數(shù)
for(i = 2;i <= sqrt(num);i += 6){
if(num % i == 0 || num % (i + 2) == 0)
return false;
}
//排除所有,剩余的是質(zhì)數(shù)
return true;
}
三、測(cè)試
對(duì)負(fù)數(shù)與0,1進(jìn)行異常處理
int main(){
int num;
bool result1,result2;
printf("請(qǐng)輸入一個(gè)正整數(shù),以-1結(jié)束: ");
scanf("%d",&num);
while(num < 2 && num != -1){
printf("輸入不合法,請(qǐng)重新輸入?。ㄕf明:素?cái)?shù)必須大于1)
");
printf("請(qǐng)輸入一個(gè)正整數(shù),以-1結(jié)束: ");
scanf("%d",&num);
}
while(num >= 2 && num != -1){
result1 = isPrime(num);
result2 = isPrime_3(num);
if(result1 == true)
printf("%d 是素?cái)?shù)
",num);
else if(result1 == false)
printf("%d 不是素?cái)?shù)
",num);
if(result2 == true)
printf("%d 是素?cái)?shù)
",num);
else if(result2 == false)
printf("%d 不是素?cái)?shù)
",num);
printf("請(qǐng)輸入一個(gè)正整數(shù),以-1結(jié)束: ");
scanf("%d",&num);
while(num < 2 && num != -1){
printf("輸入不合法,請(qǐng)重新輸入?。ㄕf明:素?cái)?shù)必須大于1)
");
printf("請(qǐng)輸入一個(gè)正整數(shù),以-1結(jié)束: ");
scanf("%d",&num);
}
}
}
讀到這里,這篇“怎么用C語言判斷一個(gè)數(shù)是否為素?cái)?shù)”文章已經(jīng)介紹完畢,想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過才能領(lǐng)會(huì),如果想了解更多相關(guān)內(nèi)容的文章,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。