怎么用C語言判斷一個數是否為素數

本文小編為大家詳細介紹“怎么用C語言判斷一個數是否為素數”，內容詳細，步驟清晰，細節處理妥當，希望這篇“怎么用C語言判斷一個數是否為素數”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

一、概念介紹

　　素數又稱為質數。一個大于1的自然數（從2開始），除了1和它本身外，不能被其他自然數整除的叫做素數，否則稱為合數。

　 0和1既不是素數也不是合數，最小的素數是2。

二、代碼

方法一：

bool is_Prime(int num){
 int i;
 
 for(i = 2;i <= sqrt(num);i++){
  if(num % i == 0)//一旦發現有因子，則返回false
   return false;
 }
 return true;
}

注意：在for循環判斷時不能忘記 i <= sqrt(num) 的等號，因為假設 p*p = n , n的因子是可以取到 sqrt(n) 的，如判斷 9 是不是素數，如果沒有等號會出現 9是素數，而實際上 9不是素數。

方法二：

關于質數分布的規律：大于等于5的質數一定和6的倍數相鄰。例如5和7，11和13,17和19等等；

證明：令x≥1，將大于等于5的自然數表示如下：

··· 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ···

可以看到，不和6的倍數相鄰的數為6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它們一定不是素數，再除去6x本身，顯然，素數要出現只可能出現在6x的相鄰兩側。因此在5到sqrt(n)中每6個數只判斷2個，時間復雜度O(sqrt(n)/3)。

在高配版和尊享版中，都是一個剪枝的思想，高配版中裁剪了不必要的偶數，尊享版中裁剪了不和6的倍數相鄰的數，雖然都沒有降低時間復雜度的階數，但都一定程度上加快了判斷的速度。

/*一種高效的方法*/
bool isPrime_3(int num){
 //兩個較小數另外處理
 if(num == 2 || num == 3)
  return true;
 //不在6的倍數兩側的一定不是質數
 if(num % 6 != 1 && num % 6 != 5)
  return false;

 int i;
 //在6的倍數兩側的也可能不是質數 
 for(i = 2;i <= sqrt(num);i += 6){
  if(num % i == 0 || num % (i + 2) == 0)
   return false;
 } 
 
 //排除所有，剩余的是質數
 return true; 
}

三、測試

　　對負數與0，1進行異常處理

int main(){
 int num;
 bool result1,result2;
 
 printf("請輸入一個正整數,以-1結束： ");
 scanf("%d",&num);
 while(num < 2 && num != -1){
  printf("輸入不合法，請重新輸入！（說明：素數必須大于1）
");
  printf("請輸入一個正整數，以-1結束： ");
  scanf("%d",&num);
 } 
 
 while(num >= 2 && num != -1){
  result1 = isPrime(num);
  result2 = isPrime_3(num);
  
  if(result1 == true)
   printf("%d 是素數
",num);
  else if(result1 == false)
   printf("%d 不是素數
",num);
 
  if(result2 == true)
   printf("%d 是素數

",num);
  else if(result2 == false)
   printf("%d 不是素數

",num);
  
  printf("請輸入一個正整數，以-1結束： ");
  scanf("%d",&num);
  while(num < 2 && num != -1){
    printf("輸入不合法，請重新輸入！（說明：素數必須大于1）
");
    printf("請輸入一個正整數，以-1結束： ");
    scanf("%d",&num);
  }
 }
}

讀到這里，這篇“怎么用C語言判斷一個數是否為素數”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。