기본적인 소수 판별 알고리즘 2가지

소수가 자기 자신과 1만을 약수로 가진다는 것은 널리 알려진 사실이다.

 

알고리즘 문제를 풀 때 어떤 수가 소수인지 아닌지 판별할 상황이 오는데 그 수가 너무 크지만 않다면 게시글에서 알려줄 두가지 방법을 이용하여 적절히 해결할 수 있다.

판별법 1. 완전 탐색을 통한 검사

자연수 N이 소수인지 아닌지 판별하는 가장 간단한 방법은 2부터 $\sqrt[]{N}$ 까지 나눠보면서 나눠지는지 아닌지 확인하는 것이다.

 

왜 모든 수를 나눠보는게 아니라 제곱근으로도 충분할까?

 

N이 합성수라고 한다면 N은 $N = ab = ba$처럼 두 자연수 a, b의 곱으로 나타낼 수 있다.

 

이 때 a와 b는 $2 \leq a \leq \sqrt[]{N}, \; \sqrt[]{N} \leq b \leq \frac{N}{2}$ 또는 $2 \leq b \leq \sqrt[]{N}, \; \sqrt[]{N} \leq a \leq \frac{N}{2}$가 되므로

 

N은 $\sqrt[]{N}$ 이하의 자연수에 나눠짐을 알 수 있다. 따라서 이러한 검사는 $\sqrt[]{N}$까지만 검사해도 충분하다.

 

이를 코드로 구현하면 다음과 같다.

Python

def is_prime(n):
    for i in range(2, round(n ** 0.5)):
        if n % i == 0:
            return False
    return True
 
N = int(input())
 
print(is_prime(N))

C / C++

#include <cmath>
#include <iostream>
 
bool isprime(int n)
{
    for (int i = 2; i <= sqrt(n); ++i)
        if (n % i == 0)
            return false;
    return true;
}
 
int main()
{
    int N;
 
    std::cin >> N;
    
    std::cout << isprime(N);
}

이 코드들의 시간 복잡도는 $O(\sqrt[]{N})$이 된다. 대부분의 알고리즘 문제의 제한 시간이 2초이고 문제에서 단 한번의 소수 판별이 필요하다고 하면 1억번($10^8$)의 연산 수행에 1초가 소요됨을 가정하고 $10^{16}$ 이내에 있는 자연수를 판별할 수 있다.

 

추가로 2를 제외한 짝수는 무조건 소수가 될 수 없다는 점을 이용해 i를 2씩 더해주도록 하면 코드의 수행 시간을 반으로 줄일 수 있다.

 

이 방법은 수가 엄청나게 크지 않고 한번만 소수 판별을 할 경우 간단하면서도 유용하게 이용할 수 있다.

 

다만 여러개의 소수를 찾아야 되는 문제라면 다음 판별법을 사용하는게 좋다.

판별법 2. 에라토스테네스의 체

에라토스테네스의 체는 엄밀히 말해 판별법은 아니고 자연수 N 이하의 모든 소수를 추출하는 방법이라고 생각하면 된다.

 

다음과 같은 자연수 테이블이 있고 소수가 아닌 수에 색을 칠한다고 해보자.

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

 

1은 소수가 아니니 제하고 2를 본다. 2는 유일한 짝수 소수이다.

 

2는 소수일 때 2의 배수들은 모두 합성수이니 이들을 모두 제거해보자.

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

 

그 다음 3을 보자. 역시 3은 소수이니 3의 배수들을 모두 제거해보자.

 

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

 

그 다음 4를 보자. 4는 이미 제거되었으니 살펴볼 필요가 없다.

 

5를 보면 5는 소수이고 마찬가지로 5의 배수들을 제거하면 된다.

 

여기서 재미있는 걸 하나 발견할 수 있는데, 이렇게 작은 수부터 시작해서 배수를 모두 거르고 나면 그 다음 걸러지지 않은 수는 무조건 소수라는 것이다.

 

그래서 이름도 에라토스테네스의 '체'다.

 

우리는 이 과정을 배열을 통해 구현할 수 있다.

 

C / C++

#include <cmath>
#include <vector>
#include <iostream>
 
using namespace std;
 
bool nonprime[10000001];
vector<int> primenumbers;
 
void sieve(int n)
{
    nonprime[0] = nonprime[1] = true;
    
    for (int i = 2; i <= n; ++i)
    {
        if (nonprime[i])
            continue;
        
        primenumbers.push_back(i);
        
        for (int j = i + i; j <= n; j += i)
            nonprime[j] = true;
    }
}
 
int main()
{
    int n;
    cin >> n;
    
    sieve(n);
    
    cout << primenumbers.size();
}

해당 코드는 에라토스테네스의 체를 통해 찾아낸 소수를 벡터 자료구조에 넣는다. 이를 통해 여러개의 소수를 빠르게 얻어낼 수 있다.

 

에라토스테네스의 체는 알고리즘 대회에서 $10^7$까지의 수까지 사용할 수 있다고 한다.^[1]

 

지금까지 소수를 판별하는 방법 중에서 대표적인 두가지를 알아보았다. 이 방법들을 학습하여 여러 문제에 이용해보자.

 

[1] : 스티븐 할림 외 1명, 「알고리즘 트레이닝 : 자료구조, 알고리즘 문제 해결 핵심 노하우」, 김진현, 인사이트(2017년), 326p.