[Algorithm] 백준 알고리즘 기초 1/2 - 소수

소수

소수는 약수가 1과 자기 자신 밖에 없는 수이다.

소수와 관련된 알고리즘은 두 가지가 있다.

1. 어떤 수 $N$이 소수인지 아닌지 판별하는 방법

2. $N$보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법

$N$이 소수가 되려면 2보다 크거나 같고, $N-1$보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

$N-2$번 연산하므로 $O(N)$의 시간 복잡도를 가진다.

• 소수 판별 구현 - $O(N)$

bool prime(int n) {
    if(n < 2) {
        return false;
    }
    for(int i = 2; i <= n - 1; i++) {
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

$N$이 소수가 되려면 2보다 크거나 같고, $\frac{N}{2}$보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

$N=a\times{b}$로 나타낼 수 있는데, $a$가 작을수록 $b$는 크다. 가능한 $a$ 중에서 가장 작은 값은 2이기 때문에, $b$는 $\frac{N}{2}$를 넘지 않는다.

$\frac{N}{2}$번 연산하므로 $O(N)$의 시간 복잡도를 가진다.

• 소수 판별 구현 - $O(\frac{N}{2})$

bool prime(int n) {
    if(n < 2) {
        return false;
    }
    for(int i = 2; i <= n / 2; i++) {
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

$N$이 소수가 되려면 2보다 크고나 같고, $\sqrt{N}$보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

$N$이 소수가 아니라면 $N=a\times{b}$로 나타낼 수 있다. 여기서 $a\leq{b}$이다. $a\gt{b}$라면 두 수를 바꿔서 항상 $a\leq{b}$로 만들 수 있다.

두 수 a와 b의 차이가 가장 작은 경우는 $\sqrt{N}$이므로 $\sqrt{N}$까지만 검사하면 된다.

컴퓨터에서 실수는 근사값을 나타내기 때문에, $\sqrt{N}$과 같은 경우는 양변을 제곱하여 $N$으로 나타낸다.

$\sqrt{N}$번 연산하므로 $O(\sqrt{N})$의 시간 복잡도를 가진다.

• 소수 판별 구현 - $O(\sqrt{N})$

bool prime(int n) {
    if(n < 2) {
        return false;
    }
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

에라토스테네스의 체

$N$이 소수인지 아닌지 알아내는데 걸리는 시간 복잡도는 $O(\sqrt{N})$이었다.

하지만, 1부터 $N$까지 범위 안에 들어가는 모든 소수를 구하는데 걸리는 시간 복잡도는 각각의 수에 대해 소수인지 검사해야 하므로 $O(\sqrt{N})$의 시간 복잡도를 가진다. 만약, 1부터 1,000,000까지 모든 소수를 구하려면 10억번을 연산해야 하므로 10초 정도의 시간이 소요된다. 이는 너무 긴 시간이다.

1부터 $N$까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다.

1. 2부터 $N$까지 모든 수를 써 놓는다.

2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.

3. 그 수는 소수이다.

4. 그 수의 배수를 모두 지운다.

• 에라토스테네스의 체를 이용한 소수 판별 구현

int prime[100];
int pn = 0;
bool check[101];
int n = 100;
for(int i = 2; i <= n; i++) {
    if(check[i] == false) {
        prime[pn++] = i;
        for(int j = i * i; j <= n; j += i) {
            check[j] = true;
        }
    }
}

1부터 $N$까지 모든 소수를 구하는 것이 목표이기 때문에, 구현할 때 바깥 for문 $i$를 $N$까지 돌린다.

안쪽 for문 $j$는 $N$의 크기에 따라서 $i^2$ 또는 $2i$로 바꾸는 것이 좋다. $i = 1,000,000$인 경우 $i^2$는 범위를 넘어가기 때문에 $2i$로 바꿔야 한다.

$O(N\log{}{\log{}{N}})$의 시간 복잡도를 가진다.

골드바흐의 추측

에라토스테네스의 체의 응용으로는 골드바흐의 추측이 있다.

골드바흐의 추측은 '2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다'는 것이다.

위의 문장에 3을 더하면 '5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다'로 바뀐다.

아직 증명되지 않은 문제이지만 $10^{18}$ 이하에서는 참인 것이 증명되어 있다.