[Algorithms/Python] 에라토스테네스의 체

소수를 대량으로 빠르게 찾는 알고리즘이다. 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 수이다.

자연수 n이 소수인지 아닌지를 판별하기 위해서는 단순히 2부터 n-1까지 반복하면서 나누어 떨어지는지 확인하면 된다. 하나라도 나누어 떨어지는 수가 존재한다면 1과 자기자신을 제외한 수 중 약수를 갖게 되는 것이므로 n은 소수가 아니다.

위의 과정을 Python 코드로 표현하면,

def is_prime_number(n):
    for i in range(2,n): # 2부터 n-1까지
        if n % i == 0: # 하나라도 나누어 떨어지는 수가 있다면
            return False # 소수가 아니다.
	
    return True

 

위의 방법은 직관적이지만 비효율적이라는 단점이 있다. 2부터 n-1까지 반복해야 하기에 $O(n)$의 시간 복잡도를 갖는다.

약수를 판단하는 데에는 기본적으로 2부터 n-1까지 모두 반복할 필요가 없다. 각 수가 갖는 약수는 해당 수의 제곱근을 기준으로 대칭을 이루기 때문이다. 16의 경우 1,2,4,8,16의 약수를 갖고 16의 양의 제곱근인 4를 기준으로 대칭을 이룬다. 즉, 16이 2로 나누어 떨어짐을 알게 된다면 8로 나누어 떨어지는 건 자동적으로 참이다. 16을 2로 나눈 몫이 8이기 때문이다.

따라서 n이 소수임을 판단하기 위해서는 2부터 n의 제곱근까지 나누어 떨어지는지만 확인하면 된다. 이 경우 n이 소수를 판별하는 데에 시간복잡도는 $O(\sqrt{n})$ 이 된다.

이를 반영하여 소수 판별 함수를 개선하면, 아래와 같이 판별 가능하다.

# 개선된 소수 판별 함수
def is_prime_number(n):
    end = int(n**(1/2))
    for i in range(2, end+1):
        if n % i == 0:
            return False
    
    return True

앞서 에라토스테네스의 체 알고리즘은 소수를 대량으로 빠르게 찾는 알고리즘이라 하였다. n이 소수인지 판별하는 것이 아니라 n이하의 소수를 찾는 것으로 목표를 바꿔보자. 방법은 다음과 같다.

1. 1부터 n을 원소로 갖는 배열 arr를 선언
2. 2부터 $\sqrt{n}$까지 나누어 떨어지면 해당 배열의 원소는 삭제함.
3. 이때 나누어 떨어지는 수는 자기자신은 제외함 (예컨대, 2로 나누어 떨어질 때 2는 삭제되어서는 안됨)

def prime_numbers(n):
    arr = [i for i in range(n+1)] # 인덱싱을 수월하게 하기 위해 0부터 배열 선언
    end = int(n**(1/2))
    for i in range(2, end+1):
        if arr[i] == 0: # 이미 소수가 아님이 판별된 수는 건너뜀
            continue
        for j in range(i*i, n+1, i): # 자기 자신을 제외한 i의 배수는 모두 0으로 처리함.
            arr[j] = 0
            
    return [i for i in arr[2:] if arr[i]]

위처럼 에라토스테네스의 체 알고리즘을 활용하여 대략 시간복잡도 $O(n\sqrt{n})$로 n 이하의 소수를 모두 구할 수 있다.