에라토스테네스의 체는 소수를 찾는 알고리즘 중 하나이다. 2부터 시작하여 차례로 배수들을 지워나가는 방식으로 소수를 찾는다.
예를 들어, 2부터 20까지의 소수를 찾는 경우를 살펴보자. 먼저 2는 소수이므로 2의 배수인 4, 6, 8, 10, 12, 14, 16, 18, 20을 제거한다. 다음으로 3은 소수이므로 3의 배수들을 살펴보는데, 6, 9, 12, 15, 18은 이미 제거되었거나 제거할 수 있으므로 3만 남긴다. 4는 이미 2의 배수로 제거되었고, 5는 소수이므로 5의 배수들을 제거하고 5만 남긴다. 이러한 과정을 반복하여 20까지의 소수를 모두 찾을 수 있다.
에라토스테네스의 체를 구현할 때는 배열을 사용하여 각 숫자의 소수 여부를 저장한다. 처음에는 모든 숫자를 소수로 간주하고, 소수가 아닌 숫자는 배열에서 제거해 나간다.
아래는 에라토스테네스의 체를 이용하여 1부터 100까지의 소수를 찾는 예제 코드이다
# 에라토스테네스의 체를 이용하여 1부터 100까지의 소수를 찾는 코드
n = 100 # 찾고자 하는 범위
sieve = [True] * (n+1) # 모든 수를 소수로 간주
for i in range(2, int(n**0.5)+1):
if sieve[i]:
for j in range(i*2, n+1, i):
sieve[j] = False # i의 배수 제거
# 소수 출력
for i in range(2, n+1):
if sieve[i]:
print(i, end=' ')
찾고자 하는 범위의 제곱근이 최대로 지워야 하는 수의 범위가 된다. 예를 들어, 100 이하의 소수를 찾는 경우, 10보다 작은 수의 배수만 지우면 된다. 이는 2부터 10까지의 수를 차례로 나열하여 2의 배수, 3의 배수, 5의 배수를 순서대로 지우면서 수행된다.
따라서 에라토스테네스의 체 알고리즘에서는 찾고자 하는 범위의 제곱근까지만 검사하면 된다. 이 범위를 넘어서는 수들은 더 이상 지울 필요가 없기 때문이다.
에라토스테네스의 체 알고리즘의 시간 복잡도는 $O(nlog(logn))$이다.
이는 주어진 범위 내의 모든 수에 대해 각 수의 배수를 지우는 작업을 수행하므로, 전체 연산 횟수가 약 $\frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \frac{n}{7} + \cdots$와 같이 진행되기 때문이다. 이때 등비수열의 합 공식을 이용하면, 이 값은 $O(nlog(logn))$로 계산된다.