C 언어 는 하나의 수가 소수 인지 아 닌 지 를 판단 한다.

개념 소개
소 수 는 질 수 라 고도 부른다.1 이상 의 자연수(2 부터)는 1 과 그 자 체 를 제외 하고 다른 자연수 에 의 해 정 제 될 수 없 는 것 을 소수 라 고 하고 그렇지 않 으 면 합 수 라 고 한다.
0 과 1 은 소수 도 합 수도 아니 고 가장 작은 소 수 는 2 이다.
코드
방법 1:

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 는 소수 가 아 닙 니 다.
방법 2:
질 수 분포 에 관 한 규칙: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 언어 가 하나의 숫자 가 소수 인지 아 닌 지 를 판단 하 는 방법 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C 언어 가 하나의 숫자 가 소수 인지 아 닌 지 를 판단 하 는 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!