[Python] 에라토스테네스의 체 (소수 구하기)

에라토스테네스의 체 (Sieve of Eratosthenes)

📌 개요

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 고안한 소수를 빠르고 효율적으로 찾는 알고리즘입니다!
특정 범위 내의 모든 소수를 한 번에 구할 수 있어 수학 및 알고리즘 문제 해결에서 널리 사용됩니다.

---

🎯 원리

에라토스테네스의 체는 다음과 같은 절차로 동작합니다:

1️⃣ 초기화 → 2부터 원하는 범위까지 모든 정수를 나열
2️⃣ 첫 소수 선택 → 가장 작은 소수 2부터 시작
3️⃣ 배수 제거 → 2의 배수를 제거 (자기 자신 제외)
4️⃣ 다음 소수 선택 → 남아있는 수 중 다음 소수 선택 & 배수 제거
5️⃣ 반복 → 위 과정을 모든 수에 대해 반복!

💡 이 과정을 거치면 남아있는 수들이 소수!

---

🔎 예시

예를 들어, 1부터 25까지의 소수를 찾는 과정을 보겠습니다.

🔢 초기 배열

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

 

🚀 2의 배수 제거

2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25

🚀 3의 배수 제거

2, 3, 5, 7, 11, 13, 17, 19, 23, 25

🚀 5의 배수 제거

2, 3, 5, 7, 11, 13, 17, 19, 23

✅ 남아있는 숫자들이 소수입니다! 🎉

---

🖥️ 구현 (Python)

아래는 주어진 범위 [N, M] 내의 소수를 찾는 Python 코드입니다.

 

import math

input = open("input.txt", "r").readline

n, m = map(int, input().split())
check = [0] * (m + 1)  # 소수 판별 배열

# 🏗️ 에라토스테네스의 체 실행
for i in range(2, int(math.sqrt(m)) + 1):
    if check[i] == 1:
        continue
    for j in range(i * 2, m + 1, i):  # i의 배수 제거
        check[j] = 1

# 🎯 결과 출력
for i in range(n, m + 1):
    if check[i] == 0 and i != 1:
        print(i)

---

⏳ 시간 복잡도

에라토스테네스의 체의 **시간 복잡도는 O(N log log N)**입니다.
🚀 단순한 소수 판별(O(N√N))보다 훨씬 빠른 알고리즘입니다!

---

🏗️ 활용

에라토스테네스의 체는 다양한 분야에서 활용됩니다:

🔐 암호학 → RSA 등 공개 키 암호 알고리즘에서 소수 생성
🔢 수학 연구 → 수론에서 소수의 분포 연구
🎯 프로그래밍 대회 → 빠른 소수 판별 문제 해결

---

🏁 결론

🔥 에라토스테네스의 체는 소수를 빠르고 효율적으로 찾는 강력한 알고리즘!
이를 활용하면 큰 범위에서도 소수를 빠르게 찾을 수 있으며,
수학적 문제 해결에도 유용합니다. 🚀