에라토스테네스의 체

에라토스테네스의 체?

첫 인상 : 이름이 어려워 보여서 멋있음.

N 이하의 소수를 구할 때 유용하게 쓰이는 소수판정 알고리즘, 자연수 i를 제외한 i의 배수를 체 처럼 걸러내면 남는 것은 전부 소수임.

에라토스테네스의 체를 왜 써야함?

BOJ PS중 소수를 판정하는 문제는 조건, 반복문을 활용
하여 간단하게 풂. 그러나 k번째 소수 구하기, 골드바흐의 추측 등 난이도가 더 올라간 소수 판정 문제를
그렇게 풀면 시간 초과 and 스파게티 코드가 됨.

즉, 에라토스테네스의 체를 사용하면 런타임이 긴 소수 판정 문제의 시간복잡도를 낮춰주고, 깔끔한 풀이 방법에 접근하기 쉬워짐.

에라토스테네스의 체 파이썬 코드

limit = (자연수)
eratos_data = [True] * (limit + 1)
eratos_data[0], eratos_data[1] = False, False

for i in range(2, int(len(eratos_data) ** 0.5)):
    if eratos_data[i]:
        for j in range(i + i, len(eratos_data), i):
            eratos_data[j] = False

• 저자가 위 코드에서 처음 든 의문점은 왜 제곱근 까지만
  탐색하면 되는지였음.

원래 이 코드를 보기 전 혼자 구현 하려했었는데
그때 시간 복잡도를 줄이려고 원래 n까지 다 탐색하던 거
n / 2으로 줄이고 여러가지 시도를 해봤었음.

So, 왜 제곱근 까지?

자연수 N은 N = a * b 라고 표현할 수 있음.
ex ) 10 = 2 * 5 or 1 * 10
그렇다면 N = m * m (m = N 의 제곱근) 라고도 가능

이때 a와 b가 자연수라면 3가지의 경우의 수 밖에 없음
A : a = m 이고 b = m
B : a < m 이고 b > m
C : a > m 이고 b < m

때문에 N = a * b, N = m * m 에서
a, b 둘 중 하나는 항상 m보다 작거나 같음
( a <= m 또는 b <= m)

그렇기 때문에 N의 모든 약수에 해당하는 a와 b가

어떠한 약수이더라도 둘 중 하나는 무조건 m이하 이므로 N의 제곱근인 m까지만 탐색하면

N이하의 모든 값에 대해 소수 판정이 가능하다.