소수 판별하기

 이 포스팅에서는 O(sqrt(N))의 시간복잡도를 가지는 판별법에 대한 설명을 할 예정입니다. 밀러라빈 팔별법, AKS알고리즘 등 고속의 알고리즘에 대한 설명을 찾으시는 분들은 건너뛰셔도 무방합니다.

 

약수의 특징 활용하기 

 약수와 배수 토픽에서 설명했던 약수의 특징을 이용하면 앞에서 사용한 알고리즘의 시간을 많이 단축할 수 있습니다. 

 소수와 약수의 특징을 조합해봅시다. 소수는 2~(N-1)범위에서 약수를 가지지 않습니다. 또한 약수가 존재하는 숫자의 약수들 중 반은 1 ~ sqrt(N)범위에 존재합니다. 즉, 소수임을 판단하기 위하여 약수를 검사할 때 2~sqrt(N)까지만 검사하면, 전체 범위에서 약수의 존재 여부를 확신할 수 있다는 말이됩니다.

 전 토픽에서 다루었던 알고리즘은 N이 소수인 경우 O(N)의 시간복잡도를 가지는 반면, 위 방법을 사용하면 N이 어떤 수던간에 2~sqrt(N)범위에서의 약수 존재여부만 검사하면 되므로 O(sqrt(N))의 시간복잡도를 가집니다. 구현은 아래와 같습니다.

bool isPrime(int n)
{
    if( n <= 1 )
        return false; //1은 소수가 아니다.
        
    if( (n&1) == 0 ) //짝수는
        return (n == 2); //2이면 true 아니면 소수아니다
        
    for(int i=3; i*i<=n; i++)
    { // i = 3 ~ sqrt(n) 까지의 홀수
        if( n % i == 0)
        {//i가 n의 약수라면
            return false; //약수존재. 소수아니다.
        }
    }
    return true; //소수이다   
}