소수 판별 알고리즘

어떤 수 n이 소수인지 판별하는 방법 중 가장 기본적인 것은

2부터 n-1까지 n에 대해 나눠보고 나눠지는 경우에는

소수가 아님을 판별하는 방법이 있다.

 

에라토스테네스 체의 특징을 이용하여 소수를 더 간단하게 구하는 방법이 있다.

예를들어 4를 소인수 분해하면 2*2가 나오고, 63을 소인수분해 해보면 3*3*7이 나온다.

이와 같이 합성수 m를 소인수분해 한 값들은 m의 제곱근보다 작거나 같음을 알 수 있다.

 

이를 이용하여 소수 판별 알고리즘을 작성하면 다음과 같다.

#include <stdio.h>
#include <math.h>
 
int main()
{
    int n;
    int i,j;
 
    printf("판별할 수를 입력하세요 : ");
 
    scanf("%d",&n);
 
    j = sqrt(n);
 
    for(i=2;i<=j;i++)
    {
        if(n%i==0)
        {
            printf("%d는 소수가 아닙니다\n", n);
            return 0;
        }
    }
 
    printf("%d는 소수입니다\n",n);
 
}

 

리눅스 환경이라면 gcc [소스파일명] -o [실행파일명] -lm 과 같은 방식으로 해주어야 한다.

-lm은 math library를 사용한다는 의미이다.