📝 강의 개요

<aside>

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

이 알고리즘은 배수를 제거하는 방식을 사용하여 소수를 빠르게 찾을 수 있습니다.

</aside>

🔍 알고리즘 원리

1. 소수란?

   • 1과 자기 자신으로만 나누어 떨어지는 수입니다.
   • 예: 2, 3, 5, 7, 11, 13, 17, ...

2. 에라토스테네스의 체 개념

   • 2부터 시작하여 특정 수의 배수를 제거하면서 남아 있는 수가 소수입니다.

3. 알고리즘 동작 방식

   예를 들어, 1부터 20까지의 소수를 구하는 과정을 살펴봅시다.

   단계	설명
   1	1은 소수가 아니므로 제외
   2	2는 소수이므로 남김, 2의 배수(4, 6, 8, …) 제거
   3	3은 소수이므로 남김, 3의 배수(6, 9, 12, …) 제거
   4	4는 이미 제거되었으므로 넘어감
   5	5는 소수이므로 남김, 5의 배수(10, 15, …) 제거
   ...	같은 과정을 반복하여 남은 숫자가 소수!

   ✨ 결과: 2, 3, 5, 7, 11, 13, 17, 19 (소수)

<aside>

알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. (보라색)

그림의 경우,

112>120

이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

</aside>

1. 그림으로 이해하기

   복사편집
   초기 상태:   1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
   2의 배수 제거: 1  2  3  X  5  X  7  X  9  X 11  X 13  X 15  X 17  X 19  X
   3의 배수 제거: 1  2  3  X  5  X  7  X  X  X 11  X 13  X  X  X 17  X 19  X
   5의 배수 제거: 1  2  3  X  5  X  7  X  X  X 11  X 13  X  X  X 17  X 19  X
   
   

   즉, 소수를 제외한 모든 수가 제거되면서 최종적으로 소수만 남습니다.

✨ 1. Python 예제 (쉬운 코드 + 주석)

# 에라토스테네스의 체를 사용하여 소수를 찾는 함수
def sieve_of_eratosthenes(n):
    # 0과 1은 소수가 아니므로 False, 나머지는 True로 초기화
    prime = [True] * (n + 1)
    prime[0] = prime[1] = False

    # 2부터 n의 제곱근까지 확인하면서 배수 제거
    p = 2
    while p * p <= n:
        if prime[p]:  # p가 소수라면
            for i in range(p * p, n + 1, p):
                prime[i] = False  # p의 배수를 모두 제거
        p += 1

    # 소수만 리스트로 반환
    return [p for p in range(n + 1) if prime[p]]

# 50 이하의 소수 찾기
n = 50
print("소수 목록:", sieve_of_eratosthenes(n))

📌 설명

• prime 리스트를 만들어 소수 여부를 저장합니다.
• 2부터 시작하여 현재 값의 배수를 제거합니다.
• 최종적으로 True인 값만 소수로 출력합니다.

✨ 2. C 언어 예제 (배열 사용)