에라토스테네스의 체

Sieve of Eratosthenes

개요

특정 범위의 소수들을 빠르게 구하는 알고리즘으로, 까지의 소수들을 에 구할 수 있습니다.

소수는 과 자기 자신을 제외한 약수를 갖지 않는 수로, 다르게 말하면 과 자기 자신을 제외한 어느 정수의 배수도 아닌 수입니다.

에라토스테네스의 체는 소수의 배수들을 제거하는 방식으로 소수를 빠르게 구합니다. 부터 까지 자연수 중에서 먼저 의 배수를 제거합니다. 의 배수를 제거합니다. 는 이미 제거되었으므로 건너뛰고, 의 배수를 제거합니다. 이처럼 소수들의 배수를 제거하는 방식으로 합성수를 걸러내어 까지의 소수들을 구합니다.

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[1] = False
    for i in range(2, n + 1):
        if not is_prime[i]:
            continue
        for j in range(i + i, n + 1, i):
            is_prime[j] = False
    return is_prime

위와 같은 방식으로 is_prime을 완성한 뒤, is_prime[i]가 참이면 i는 소수입니다.

시간 복잡도의 증명

꼭 알아야 하는 것은 아니며 넘어가도 됩니다.

까지 의 배수의 개수는 로 나타낼 수 있습니다.
그렇다면 까지 소수들의 배수의 개수는 로 나타낼 수 있습니다.
까지 소수의 개수를 이라 합시다. 소수가 하나 추가될 때 마다 소수의 역수를 더해 주는 것이라 생각하여 적분으로 바꿀 수 있습니다.

소수 정리에 따르면 입니다. 대신 를 대입하면

라 두고 치환합시다. 입니다.

따라서 소수의 역수들의 합은 에 점근하고 에라토스테네스의 체의 시간 복잡도는 이 됩니다.

문제

• 1929번: 소수 구하기 풀이