파이썬으로 구현하는 다양한 소수 판별 알고리즘 (완전탐색부터 에라토스테네스의 체까지)

파이썬으로 소수를 찾는 알고리즘 3가지에 대해 알아봅시다.

 

 

 

1. 완전 탐색 방법

첫번째 방법은 완전 탐색 방법으로 소수인지 판별하는 방법입니다. 소수는 1과 자기 자신만을 약수로 갖는 수이기 때문에 2부터 자기 자신보다 1작은 수까지 모두 나누어보며 나누어 떨어지는지 확인하면 소수인지 알 수 있습니다.

# 1. 완전 탐색 방법
def is_prime_number(x):
    for i in range(2, x):
        if x % i == 0:
            return False
    return True

이 알고리즘을 사용하면 시간복잡도는 $O(N)$입니다. 2부터 N-1까지 반복문을 돌면서 판별하기 때문입니다.

 

 

 

2. 제곱근까지만 확인해보자

두번째 방법은 약수끼리 대응시켜 곱했을 때 결국 자기 자신이 나온다는 점을 이용한 알고리즘입니다. 아래 그림으로 예시를 들어보겠습니다. 16의 약수는 1, 2, 4, 8, 16입니다. 이전 알고리즘에서 우리는 2부터 15까지로 모두 나누어보았는데, 약수끼리 곱하면 결국 자기자신이 나온다는 점을 알면 그럴 필요가 없습니다. 16을 2로 나누는 것이나 8로 나누는 것이나 소수 판별에서는 결국 똑같다는 거죠!

그래서 우리는 가운데에 있는 약수, 즉 16의 제곱근까지만 나누어보면서 소수인지 판별하는 알고리즘을 사용할 수 있습니다.

출처: 이것이 코딩테스트다 (나동빈, 한빛미디어)

 

# 2. 제곱근까지만 확인하는 방법
import math

def is_prime_number(x):
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

이 알고리즘을 사용하면 시간복잡도는 $O(N^{\frac{1}{2}})$ 입니다. 확인해야할 범위가 N에서 N의 제곱근($N^{\frac{1}{2}}$)로 줄어들었습니다.

 

 

 

3. 에라토스테네스의 체

에라토스테네스의 체 알고리즘으 $N$보다 작거나 같은 모든 소수를 찾을 때에 유용하게 사용할 수 있는 알고리즘입니다. 이 알고리즘은 아직 처리하지 않은 수 중 가장 작은 수의 배수를 모두 제거해가면서 소수만 남겨놓는 방법입니다. 이 때 가장 작은 수는 2번의 알고리즘과 마찬가지로 $N$의 제곱근까지만 확인합니다. 

# 3. 에라토스테네스의 체 (Sieve of Eratosthenes)
n = 1000    # 2부터 1000까지의 모두 수에 대하여 소수 판별
array = [True for i in range(n + 1)]    # 소수인지 아닌지 판별한 값을 담는 배열(0과 1은 소수가 아님)

for i in range(2, int(math.sqrt(n)) + 1):
    if array[i] == True:     # i가 소수인 경우(남은 수인 경우)
        # i를 제외한 i의 모두 배수를 지우기
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1

이 알고리즘의 시간복잡도는 $O(Nlog(logN))$으로 거의 선형의 시간복잡도를 갖습니다. 그러나 소수인지 아닌지 판별한 boolean 값을 담는 배열이 필요하므로 $N$이 커지면 그만큼 필요한 메모리도 커진다는 단점이 있습니다.