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

에라토스테네스의 체는 특정 숫자 범위 내의 모든 소수를 찾는 간단하고 효율적인 알고리즘이다. 마치 체로 거르듯 소수가 아닌 수들을 걸러낸다고 해서 '체'라는 이름이 붙었다.

---

1단계: 준비 🧮

먼저, 소수를 찾고자 하는 범위의 숫자들을 모두 나열한다. 예를 들어, 1부터 120까지의 소수를 찾는다면 1부터 120까지의 숫자를 종이에 쭉 적어 본다.

---

2단계: 소수 걸러내기 篩

1. 시작: 2는 가장 작은 소수이므로 동그라미를 친다. 그리고 2의 배수들은 모두 소수가 아니므로 지운다 (4, 6, 8, 10...).
2. 다음 소수: 지워지지 않고 남아있는 다음 숫자는 3이다. 3에 동그라미를 치고, 3의 배수들은 모두 지운다 (6, 9, 12, 15...).
3. 반복: 이 과정을 계속 반복한다. 지워지지 않고 남아있는 다음 숫자는 5. 5에 동그라미를 치고 5의 배수를 모두 지운다. 그다음은 7... 이렇게 남아있는 숫자의 배수들을 계속 지워나간다.

---

3단계: 완성 ✨

이 과정을 범위의 마지막 숫자의 제곱근까지만 반복하면 된다. 120의 제곱근은 약 10.95이므로, 10까지의 소수(2, 3, 5, 7)의 배수들만 지워도 충분하다. 이 과정을 모두 마치고 남은 숫자들, 즉 동그라미 친 모든 숫자들이 바로 소수이다.

이 방법은 약수들을 일일이 나눠보지 않아도 되기 때문에 아주 효율적이다. 컴퓨터 프로그래밍에서 소수를 찾는 가장 기본적인 방법으로 널리 사용된다.

 

수식으로 풀어서 설명한다면

 

에라토스테네스의 체는 특정 범위 내의 모든 소수를 찾는 알고리즘이다. 이를 수식으로 나타내기보다는, 알고리즘의 절차를 수학적 기호와 논리로 표현하는 것이 더 정확하다.

1단계: 초기화

먼저, 소수를 찾고자 하는 범위 [2,n] 내의 모든 정수를 포함하는 리스트나 배열 A를 만든다. 처음에는 모든 수가 소수 후보라고 가정한다.

• A={2,3,4,...,n}
• Ai​=true for all i∈[2,n]

2단계: 소수 판별 및 배수 제거

p를 2부터 시작하여 $\sqrt{n}$까지 반복하며, 소수 후보(즉, 아직 지워지지 않은 수)인 p를 찾아 그 배수를 모두 제거한다.

• 반복문: p를 2부터 $\sqrt{n}$까지 증가시키면서 다음 단계를 수행한다.
• 조건: 만약 Ap​가 true (즉, p가 소수 후보)라면, p는 소수이다.
• 배수 제거: p가 소수일 경우, p2부터 n까지의 p의 모든 배수를 '소수가 아님'으로 표시한다.
  • Ak​=false for all k=p2,p2+p,p2+2p,...,≤n
  • 참고: p의 배수를 p부터 지우지 않고 p2부터 지우는 이유는, p보다 작은 소수들의 배수는 이미 그 소수들에 의해 지워졌기 때문이다. 예를 들어, 2의 배수는 이미 2에 의해 지워졌고, 3의 배수 중 6, 9 등은 2나 3에 의해 이미 지워졌다.

3단계: 결과

위 과정이 끝나면, A에서 '참'으로 남아있는 모든 정수가 소수이다.

• 결과: {p∈[2,n]∣Ap​=true}

---

예시: n=30

• 초기 리스트: [2,3,...,30]
• p=2: 2는 소수이다. 2의 배수인 4,6,8,...,30을 모두 지운다.
• p=3: 3은 남아있으므로 소수이다. 3의 배수인 9,12,15,...,30을 지운다. (12, 18 등은 이미 지워졌음)
• p=4: 이미 지워졌으므로 넘어간다.
• p=5: 5는 남아있으므로 소수이다. 5의 배수인 25,30을 지운다.
• 반복 종료: 30​≈5.47 이므로 5까지의 소수만 처리하면 된다.
• 결과: 지워지지 않고 남은 수들 ${2, 3, 5, 7, 11, 13, 17, 19, 23, 29}$이 소수이다.