[알고리즘][파이썬] 소수 판별 알고리즘(에라토스테네스의 체)

소수란?

2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수를 말한다.

 

기본적인 소수 판별 방법

def is_prime(num):
    # 2부터 (num - 1)까지의 모든 수 확인.
    for i in range(2, num):
        # 하나라도 i로 나눠진다면 False를 반환.
        if num % i == 0:
            return False
    return True

이 때 시간복잡도는 O(n)이므로 n의 크기가 크면 비효율적이다. 이보다 좀 더 효율적인 방법은 n - 1까지가 아닌 n의 제곱근까지만 확인하는 것이다.

 

이렇게 해도 되는 이유는 무엇일까? 예를 들어 16의 약수 [1, 2, 4, 8, 16]이 있다고 해보자.

잘 살펴보면 가운데에 있는 수를 기준으로 대칭적으로 곱해 16을 만들 수 있다. 따라서 소수의 절반에 해당하는 제곱근까지만 살펴보면 소수 판별이 가능하다.

 

제곱근까지만 확인해 소수 판별

import math

def is_prime(num):
    # 2부터 num의 제곱근까지의 모든 수 확인.
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

개선된 알고리즘의 시간 복잡도는 O(n^(1/2))이다. 하지만 이는 여러 수에 대한 소수 판별에 비효율적일 수 있다.

이런 경우 에라토스테네스의 체라는 알고리즘을 활용한다.

 

에라토스테네스의 체

특정 범위에 대한 소수 판별에 유리하다. 이는 아래와 같은 과정을 거친다.

 

1. 2부터 n까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다(i는 제거하지 않는다.).
4. 더이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

자세한 내용은 아래 코드를 참조하자.

에라토스테네스의 체를 이용한 특정 범위에 대한 소수 판별

import math

def is_prime(n):
    # 2부터 n까지의 모든 수에 대해 소수 판별
    array = [True for i in range(n + 1)]  # 처음엔 모든 수가 소수(True)인 것으로 초기화(0, 1은 제외)

    # 에라토스테네스의 체
    # 2부터 n의 제곱근까지의 모든 수를 확인
    for i in range(2, int(math.sqrt(n)) + 1):
        # i가 소수인 경우(남은 수인 경우)
        if array[i] == True:
            # i를 제외한 i의 모든 배수를 지우기
            j = 2
            while i * j <= n:
                array[i * j] = False
                j += 1

    return [i for i in range(2, n + 1) if array[i]]

에라토스테네스의 체 알고리즘의 시간 복잡도는 O(nlogn)으로 사실상 선형 시간에 동작할 정도로 빠르다. 하지만 n만큼의 메모리를 저장하고 기억해야하므로 주의해야 한다.

 

n이 1,000,000 이내로 주어지는 경우에 활용하는 것이 좋다. (이론상 400만번 정도의 연산이고 메모리도 충분하다.)