c언어 소수 구하기

임의의 정수를 입력받아 소수인지를 확인하를 프로그램를 작성하시오.

 

소수란 1보다 큰 자연수로 1과 자기 자신의 수로만 나누어 떨어지는 수를 의미한다. 예를 들어 4는 1과 자기 자신의 수 4뿐만 아니라 2로 나누어 떨어지므로 소수가 아니고 5는 1과 자기 자신의 수 5로만 나누어 떨어지므로 소수가 됩니다.

 

위 소수의 설명처럼 프로그램을 두 가지 방식으로 코딩 할 수 있습니다.

 

첫번째 방식

1부터 자기 자신까지 1씩 증가하면서 나누어 떨어지는 횟수를 구하여 두 번이면 소수라고 출력하는 방식으로 코딩 할 수 있습니다.

 

두 번째 방식 (비슷한 방식)

1과 자기 자신수를 뺀 나머지 숫자를 비교하여 소수 인지 확인하는 방법입니다. 즉 2부터 1씩 증가하면서 n-1( n : 자기 자신의 수 )번째까지 나누어 보고 이때 한 번도 나누어 떨어지지 않으면 소수로 출력하는 코딩 방식 입니다.

 

지금부터 각각의 방식으로 코딩하여 보겠습니다.

소스 코드(첫 번째 방식)	소스 코드(두 번째 방식)
#include <stdio.h> int main(void) {     int n, i, j, cnt = 0;     printf("정수 입력 : ");     scanf("%d", &n);     for (i = 1; i <= n; i++)     {         if (n % i == 0)             cnt++;     }     if (cnt == 2)         printf("%d는 소수 입니다.", n);     return 0; }   실행 결과] 정수 입력 : 5 5는 소수입니다.	#include <stdio.h> int main(void)  {      int n, i, j, cnt = 0;      printf("정수 입력 : ");      scanf("%d", &n);      for (i = 2; i <= n-1; i++)      {          if (n % i == 0)              cnt++;      }      if (cnt == 0)          printf("%d는 소수 입니다.", n);      return 0;  }   실행 결과] 정수 입력 : 5 5는 소수입니다.

위 소스코드는 소수 구하기 코딩으로 숫자가 크면 클수록 처리하는 양이 많아짐으로 처리 속도가 느려집니다. 그래서 소수를 구하는 방법에는 n의 제곱근까지 비교하는 방법도 있습니다. 예를 들어 4는 2까지 비교하고 9는 3까지 비교하고 16은 4까지 비교하고 25는 5까지만 비교하면 소수 인지 확인이 가능합니다. 각각의 숫자를 보면 4, 9, 16, 25는 양의 제곱근 까지만 비교한다는 것을 알 수 있습니다. 

 

자 지금부터 다시 코딩을 해 보겠습니다. ( 처리 속도 단축하기 )

소스코드	실행 결과
#include <stdio.h> #include <math.h> int main(void) {     int n, i, j, cnt = 0, su;     printf("정수 입력 : ");     scanf("%d", &n);     su = sqrt((float)n);     //sqrt()양의 제곱근함수      for (i = 2; i <= su; i++)     {         if (n % i == 0)             cnt++;     }     if (cnt == 0)         printf("%d는 소수 입니다.", n);     return 0; }	정수 입력 : 5 5는 소수입니다.

소스 코드1

소스 코드2

#include <stdio.h> #include <math.h> int main(void) {     int n, i, j, cnt = 0, su;     printf("정수 입력 : ");  scanf("%d", &n);     i = 2;     while (1)     {         if (i <= sqrt((float)n))         {             if (n % i == 0)             {                 break;             }             i++;         }         else         {             printf("%d는 소수 입니다.", n);             break;         }     }     return 0; } 실행 결과] 정수 입력 : 5 5는 소수입니다.

#include <stdio.h> #include <math.h> int main(void) {     int n, i, j, cnt = 0, su;     printf("정수 입력 : ");     scanf("%d", &n);     su = sqrt((float)n);     //sqrt()양의 제곱근함수      i = 2;     do     {         if (n % i == 0)             break;         i++;     } while (i <= su);     if (su < i)         printf("%d는 소수 입니다.", n);     return 0; }   실행 결과] 정수 입력 : 5 5는 소수입니다.

 

소수 구하기 소스코드를 가지고 순서도를 그리면 아래 그림과 같이 작성 할 수 있습니다.