教你用C語言判斷一個數(shù)是否為素數(shù) 詳細方法解析

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;
}

/*一種高效的方法*/
bool isPrime_3(int num){
 //兩個較小數(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; 
}

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

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

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