소수 판별 알고리즘

소수 (Prime Number)

소수란? 1보다 큰 자연수 중에서, 1과 자기 자신으로만 나누어 떨어지는 숫자를 말한다. 즉, 약수가 2개인 자연수이다. 소수는 2, 3, 5, 7, 11, … 등으로 무한히 많으며, 규칙성이 아직 증명되지 않았다.

 

소수 판별법

만약, 특정 숫자 N이 소수인지 아닌지를 확인하는 문제를 해결한다고 하자. 소수의 정의에 의해서 소수는 1과 자기 자신으로만 나누어 떨어지므로, 반대로 2부터 자기 자신보다 1 작은 값까지는 나누어 떨어지지 않는다는 것을 알 수 있다. 따라서, N이 소수인지 여부를 판단하려면, 2부터 N-1까지 모든 숫자에 대해서 나누어 떨어지는지를 확인하는 방법을 사용할 수 있다.

def is_prime(N: int) -> bool:
    for i in range(2, N):
        if N % i == 0:
            return False
    return True

이러한 방법은 쉽게 구현할 수 있지만, 시간복잡도가 $O(N)$이므로 여러 개의 숫자에 대해서 소수인지 여부를 판정하기에는 시간복잡도가 크다.

 

합성수 N이 있다고 한다면, 1을 제외한 가장 작은 약수는 $\sqrt N$ 이하일 수 밖에 없다. 만약 $x$가 1을 제외한 $N$의 가장 작은 약수라면, $\frac{N}{x}$ 또한 $N$의 약수이고, 아래와 같이 $x \le \sqrt N$임을 보일 수 있다.

 

$$ \begin{align*} x \le \frac{N}{x} \\ x^2 \le N \\ x \le \sqrt N \\ \end{align*} $$

 

따라서, N이 소수인지 여부를 판정하기 위해서는 2부터 $\sqrt N$까지의 수로 나누어 떨어지는지를 확인하면 된다. 따라서 해당 방법은 시간복잡도가 $O(\sqrt N)$이 된다.

def is_prime(N: int) -> bool:
    for i in range(2, int(N**0.5)):
        if N % i == 0:
            return False
    return True

 

에라토스테네스의 체

N까지의 모든 자연수에 대해서 각 숫자들이 소수인지 아닌지를 판별해야 하는 경우도 존재한다. 만약, 위의 소수 판정법을 사용하면 전체 숫자들이 소수인지 아닌지를 판정하기 위해서는 $O(N\sqrt N)$만큼의 시간이 소모된다.

 

이때, 에라토스테네스의 체를 이용하면 N까지의 모든 소수를 빠르게 찾을 수 있다. 에라토스테네스의 체는 크게 아래와 같이 동작한다.

1. 2부터 N까지의 모든 숫자를 우선 소수라고 가정하자. (1은 소수가 아니므로 제외한다.)
2. 이때, 2의 모든 배수는 소수가 아닌 합성수이므로 소수가 아님을 알 수 있다.
3. 소수로 가정된 다음 숫자인 3 또한 마찬가지로 모든 배수가 소수가 아님을 알 수 있다.
4. 4는 이미 합성수로 판정되었기 때문에, 가정된 다음 숫자인 5에 대해서 같은 방식으로 동작한다.
5. 모든 N에 대해서 계속 진행한다.

def prime_list(N: int) -> List:
    check_prime = [True] * (N+1)
    for num in range(2, N+1):
        if check_prime[num]:
            for multiple in range(num*2, N+1, num):
                check_prime[multiple] = False
    return [p for p in range(2, N+1) if check_prime[p]]

이때, 에라토스테네스의 체를 이용해서 N까지의 소수를 알고 싶을 때, N까지 모든 수의 배수를 전부 확인해 볼 필요는 없다. 만약, N보다 작은 합성수 M이 $M = a\times b$라면, $N \gt M$이므로 두 숫자 $a, b$ 중 적어도 하나는 $\sqrt N$보다 작은 수 이다. 따라서, N보다 작은 모든 합성수 M에 대해서 해당 합성수의 약수 중 하나는 적어도 $\sqrt N$보다 작다는 의미이므로 소수 판별법에서와 마찬가지로 2부터 $\sqrt N$까지에 대해서만 배수를 확인하면 된다.

 

또한, 특정 수 $x$가 소수일 때, $x \times 2$부터 시작하는 것이 아니라, $x \times x$부터 값을 제거해 나가도 된다. 만약, $x \times x$보다 작은 수가 $x$의 배수라고 한다면, $2 \times x$의 경우와 같이 이미 이전 숫자를 제거할 때 제거되었을 것이다. 즉, $i \times x$에서 $i < x$인 경우까지는 이미 검사되었으므로, $x^2$인 경우부터 제거하면 된다.

위와 같은 개선점들을 반영한 에라토스테네스의 체는 아래와 같이 구현될 수 있다.

def prime_list(N: int) -> List:
    check_prime = [True] * (N+1)
    for num in range(2, int(N**0.5)):
        if check_prime[num]:
            for multiple in range(num**2, N+1, num):
                check_prime[multiple] = False
    return [p for p in range(2, N+1) if check_prime[p]]

해당 알고리즘의 시간 복잡도는 $O(N\log\log N)$으로, 거의 $O(N)$과 같다고 볼 수 있다. N이 5천만인 경우에 0.5초 정도밖에 걸리지 않는 매우 효율적인 알고리즘으로 볼 수 있다.

 

소인수분해 (Prime Factorization)

소인수분해는 특정한 자연수를 소수의 곱으로만 나타낸 것이다. 이러한 표현법은 특정 숫자에 대해서 단 하나만 존재한다.

특정 숫자 N을 소인수분해하는 방법은 아래와 같다.

1. 2부터 시작해서, 숫자 $i$에 대해서 $N$을 $i$로 나누었을 때, 나누어 떨어지는지를 확인한다.
2. 나누어 떨어진다면, $N \leftarrow N / i$으로 대체하여 나누어 떨어지지 않을때 까지 반복한다.
3. 나누어 떨어지지 않았을 때, 다음 숫자 $i+1$에 대해서 다시 반복한다.

소인수분해 또한 마찬가지로, $N < i \times i$가 될 때까지만 진행하면 된다. 따라서, 소인수분해 알고리즘도 $O(\sqrt N)$의 시간복잡도를 가질 수 있다.

def prime_factorization(N: int):
    for i in range(2, int(N**0.5)):
        while N % i == 0:
            print(i)
            N /= i
    if N > 1:
        print(int(N))

 

다른 방법은 위의 에라토스테네스의 체를 이용하는 것이다, 소인수분해를 하고자 하는 수 N보다 작은 모든 소수는 위의 에라토스테네스의 체를 통해서 구해놓았다고 가정하자. 그렇다면 아래와 같이 구해진 소수에 대해서만 계산할 수 있다.

def prime_factorization(N: int):
    prime_nums = prime_list(N)
    for prime_num in prime_nums:
        while N % prime_num == 0:
            print(prime_num)
            N /= prime_num

 

References

• https://loosie.tistory.com/267
• https://www.algodale.com/algorithms/sieve-of-eratosthenes/
• https://cherryrain.tistory.com/102