[Algorithm] 에라토스테네스의 체

에라토스테네스의 체란?

에라토스테네스의 체(Sieve of Eratosthenes)는 주어진 숫자까지의 소수를 찾기 위한 효율적인 알고리즘입니다. 이 알고리즘은 고대 그리스의 수학자 에라토스테네스(Eratosthenes)에 의해 개발되었습니다. 이제 이 알고리즘의 동작 방식과 Node.js에서 어떻게 구현할 수 있는지 설명드릴게요.

에라토스테네스의 체 동작

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

• 이 표는 에라토스테네스의 체 알고리즘의 각 단계를 명확하게 설명합니다. 각 단계에서 소수를 찾고, 그 소수의 배수를 제거하는 과정을 반복하여 최종적으로 모든 소수를 구합니다.

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

구현

function sieveOfEratosthenes(limit) {
  // 0과 1은 소수가 아니므로 제외
  const isPrime = new Array(limit + 1).fill(true).fill(false, 0, 2);

  // 소수 판별 알고리즘
  for (let i = 2; i <= Math.sqrt(limit); i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= limit; j += i) {
        isPrime[j] = false;
      }
    }
  }
  
  return isPrime;
}

시간 복잡도 분석

알고리즘의 주된 시간 소모는 내부의 중첩된 루프에서 발생합니다.
1. 외부 루프: $𝑖 = 2$부터 $𝑖 ≤ \sqrt{n}$까지의 숫자를 반복합니다. 이 반복은 최대 $\sqrt{𝑛}$ 번 수행됩니다.
2. 내부 루프: 각 소수 $𝑖$에 대해, $i^2$부터 $n$까지의 숫자 중 $i$의 배수를 false로 설정합니다.

내부 루프의 반복 횟수를 계산해보면, 각 소수 $i$에 대해 $\frac{n}{i}$번 수행됩니다. 이를 모든 소수에 대해 합산하면 다음과 같은 수식이 됩니다:

$\sum_{i=2}^{\sqrt{n}} \frac{n}{i}$

이 합을 대략적으로 계산하면 이 됩니다. 이는 소수의 밀도와 관련이 있습니다.

따라서, 전체 알고리즘의 시간 복잡도는 $O(n \log \log n)$이 됩니다. 이 시간 복잡도는 $n$이 매우 큰 경우에도 비교적 효율적입니다.

참고자료

• [wikipedia]에라토스테네스의 체
• [JS] 에라토스테네스의 체 - 소수 판별