本篇文章將和大家分享如何使用C語言代碼來判斷一個(gè)數(shù)是否為素?cái)?shù)的內(nèi)容，來幫助大家理解C語言中的循環(huán)和判斷結(jié)構(gòu)的知識(shí)，以下是詳情內(nèi)容，供大家學(xué)習(xí)參考。
一、概念介紹
素?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);
}
}
}四、截圖
以上就是關(guān)于C語言代碼判斷一個(gè)數(shù)是否為素?cái)?shù)的方法詳解的文章，想要了解更多關(guān)于C語言基礎(chǔ)練習(xí)的實(shí)例內(nèi)容，推薦大家直接搜索C語言練習(xí)，里面包括了許多有關(guān)于C語言實(shí)例練習(xí)的題目。
