에라토스테네스의 체

에라토스테네스의 체는 2부터 N까지의 자연수 중에서 소수를 빠르고 효율적으로 찾는 대표적인 알고리즘입니다. 이 방법은 소수가 아닌 수(합성수)를 체로 걸러내듯이 제거해 나가면서 소수만 남기는 방식입니다.

동작 원리 요약
1. 2부터 N까지 모든 수를 나열
2. 남아있는 수 중 가장 작은 수(i)를 소수로 판정
3. i의 배수(2i, 3i, 4i, ...)를 모두 제거
4. 이를 N의 제곱근까지 반복

이 과정을 거치면 남아있는 수가 모두 소수입니다.

 

코드 예시

n = 100  # 2부터 100까지 소수 구하기
prime = [True for _ in range(n + 1)]  # 소수 여부를 저장하는 리스트

for i in range(2, int(n**0.5) + 1):
    if prime[i]:
        for j in range(i * 2, n + 1, i):  # i의 배수들은 소수가 아님
            prime[j] = False

# 소수 출력
for i in range(2, n + 1):
    if prime[i]:
        print(i, end=' ')

시간 복잡도  
O(nloglogn)으로, 매우 효율적

한 번에 여러 소수를 구할 때 특히 빠르다.
특정 범위의 소수 개수, 소수의 합 등 다양한 문제에 응용 가능