에라토스테네스의 체

에라토스테네스의 체?

에라토스테네스의 체(Sieve of Eratosthenes)는 주어진 범위 내에서 모든 소수를 찾는 알고리즘입니다.

이 알고리즘은 소수의 배수를 제거하는 방식으로 동작하며, 시간 복잡도는 O(n log log n)입니다.

(소수란 1과 자기 자신만을 약수로 가지는 수)

---

알고리즘 설명

1. 2부터 n까지의 자연수를 나열합니다.
2. 가장 작은 수인 2를 소수로 선택합니다.
3. 2를 제외한 2의 배수들을 모두 지웁니다.
4. 다음 남은 수 중 가장 작은 수를 소수로 선택하고, 그 수의 배수들을 모두 지웁니다.
5. 이 과정을 반복하여 선택된 소수의 배수를 모두 제거합니다.
6. 더 이상 지울 배수가 없으면 남아 있는 수들이 모두 소수입니다.

 

구현 코드

def eratosthenes_sieve(n):
    # 0과 1은 소수가 아니므로 False로 설정
    sieve = [True] * (n + 1)
    sieve[0] = False
    sieve[1] = False
    
    # 2부터 sqrt(n)까지의 수들의 배수를 제거
    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:  # i가 소수라면
            # i의 배수들을 False로 표시
            for j in range(i * i, n + 1, i):
                sieve[j] = False
    
    # 소수들만 리스트로 반환
    return [i for i in range(2, n + 1) if sieve[i]]

# 사용 예시
n = 50
print(eratosthenes_sieve(n))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]