[알고리즘] 에라토스테네스의 체

에라토스테네스의 체란 수학에서 소수를 찾는 방법입니다.

대량의 소수를 찾아야할 때 효과적이며,

소수를 직접 찾는 것이 아니라 일정 범위를 정해놓고 소수가 아닌 수를 지워나가는 것에 가깝습니다.

구현 순서

1. 소수를 판별할 범위 만큼 배열을 할당
2. 2부터 시작해서 범위 최대값의 제곱근까지 루프를 돌면서 소수일 때, 현재 수를 제외한 그 수의 배수에 해당하는 수를 지움(이미 지운 수는 건너뜀)
3. 남아있는 수는 전부 소수

제곱근까지만 확인해도 되는 이유는?

소수를 판별할 범위가 2 ~ n 까지라고 하면, n의 약수는 \(n^{0.5}\)이하이므로 \(n^{0.5}\)까지만 탐색합니다.

결론적으로 제곱근 이상 수들은 이미 한번 지운 것들을 재방문 하는게 됩니다.

코드

n = 1000
is_prime = [True] * (n + 1)  # 초기화
is_prime[0], is_prime[1] = False, False
for i in range(2, int(n ** 0.5) + 1):  #
    if is_prime[i]:  # 소수일 때
        for j in range(i + i, n, i):  # 소수가 아닌 것을 지운다
            is_prime[j] = False

 

Ref.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전