에라토스테네스의 체(Sieve of Eratosthenes)는 소수 판별법(Primality Test)에 쓰이는 알고리즘 중 하나이다.
특히, 많은 양의 소수를 한 번에 얻어낼 때 유용하게 사용할 수 있다.

우선 에라토스테네스의 체를 이용하지 않고, 인자로 받은 숫자가 소수인지 판별하는 함수를 Python으로 작성한 코드를 보도록 하자.

def is_prime(num: int) -> bool:
    if num < 2:
        return False
    for i in range(2, int(num ** (1/2)) + 1):
        if num % i == 0:
            return False
    return True

# N = 100
# print([num for num in range(2, N + 1) if is_prime(num)])

is_prime함수는 num이 소수이면 True, 아니면 False를 반환한다.
num이 2부터 $\sqrt{num}$ 까지의 모든 숫자로 나누어 떨어지지 않으면 num은 소수라는 사실을 이용한 알고리즘이다.

이러한 알고리즘은 판별하고자 하는 숫자들의 개수(N)가 적거나, 판별하고자 하는 숫자들의 값 자체가 작은 경우에 대해 유용하다.

그러나 브루트 포스답게, N이 커질수록 특히 비효율적이다.
2부터 N 사이의 숫자 num을 is_prime함수의 인자로 넘겨줄 때마다 최대 $\sqrt{num}$ 까지의 숫자를 매번 나누어보아야 하기 때문이다.
따라서 1부터 N까지의 숫자를 판별한다고 할 때, O(N$\sqrt{N}$)이 걸린다.
이때 에라토스테네스의 체를 활용해 시간 복잡도를 줄일 수 있다.

---

에라토스테네스의 체

에라토스테네스의 체의 원리는 다음과 같다.

1) 소수를 구하고자 하는 구간의 모든 수들을 2부터 끝(N)까지 나열한다.
2) 맨앞에 놓인 숫자 2는 소수이다. 2의 배수들을 모두 지운다.
3) 그 후, 맨앞에 놓인 3은 소수이다. 3의 배수들을 모두 지운다.
4) 그 후, 맨앞에 놓인 5는 소수이다. 3의 배수들을 모두 지운다.
5) 위의 과정을 맨앞에 놓인 $\sqrt{N}$ 이하의 숫자들에 대해 반복한다.

1.

n = 100
is_prime = [False, False] + [True] * (n - 1)

for i in range(2, int(n ** (1/2)) + 1):
    if is_prime[i]:
        for multiple in range(i * i, n + 1, i):
            is_prime[multiple] = False

# print([i for i in range(2, n + 1) if is_prime[i]])

2.

n = 100
is_prime = set(range(2, n + 1))

for i in range(2, int(n ** (1 / 2)) + 1):
    if i in is_prime:
        is_prime -= set(range(i * i, n + 1, i))

# print([i for i in range(2, n + 1) if i in is_prime])

위는 에라토스테네스의 체를 Python으로 구현한 코드이다.
중첩 반복문에서 k의 범위가 num * num으로 시작하는 이유는, 이미 num x (num - 1)까지의 숫자들은 지워져 있기 때문이다.
가령 num = 5일 때, 10, 15, 20은 각각 2, 3, 2의 배수로 지워져 있을 것이다.

증명은 꽤나 어렵다고 하는데, O(N log log N)의 시간 복잡도를 갖는다.
거의 O(N)에 가까울 정도로 시간 복잡도에서 이점을 가지지만, 메모리를 추가적으로 차지한다는 단점 역시 존재한다.
따라서 상황에 맞게 소수 판별법을 잘 선택하는 것이 좋겠다.