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

에라토스테네스의 체 (Sieve of Eratosthenes) 알고리즘에 대해 정리한 페이지입니다.

Posted Mar 25, 2024

By HyunJinNo

Tags

Algorithm

1. 개요

에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘에 대해 정리한 페이지입니다.

2. 에라토스테네스의 체 (Sieve of Eratosthenes) 알고리즘

2.1. 개념

에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘은 주어진 정수 n 이하의 모든 소수를 효율적으로 찾는 알고리즘입니다. 에라토스테네스의 체 알고리즘의 시간 복잡도는 O(N log(log N))으로 매우 빠르기 때문에 대부분의 경우 빠르게 소수를 찾을 수 있습니다.

2.2. 구현

에라토스테네스의 체 구현은 다음과 같은 과정으로 이루어집니다.

1. 먼저 2부터 n까지의 수를 전부 한 목록에 작성합니다.
2. 그 다음에 이 목록에서 지워지지 않은 수들을 순회하며 각 수의 배수를 지우는 과정을 반복합니다. 이 때 지워지지 않은 수를 찾을 때 n이 아니라 sqrt(n) (i * i <= n)까지만 찾습니다.
3. i의 배수들을 모두 지울 때 2 x i 에서 시작하는 것이 아니라 i x i 부터 시작하면 계산하는데 시간을 단축할 수 있습니다.
4. 이와 같은 과정을 반복하고 나면 결과적으로 남은 수들은 모두 소수가 됩니다.

예를 들어 1000 이하의 모든 소수를 구하는 방법은 다음과 같습니다.

1. 먼저 2부터 n까지의 수를 전부 한 목록에 작성합니다.

Tips

Array(n + 1) 이 아니라 new Uint8Array(n + 1) 을 사용하면 약 8배 더 적은 메모리를 사용하도록 메모리 사용량을 줄일 수 있습니다. 다만 false를 저장하면 실제로는 0이, true를 저장하면 실제로는 1이 저장된다는 점을 주의해야 합니다.

1const n = 1000;
2const isPrime = new Uint8Array(n + 1).fill(true);
3isPrime[0] = false; // 0은 소수가 아닙니다.
4isPrime[1] = false; // 1은 소수가 아닙니다.

2. 그 다음에 이 목록에서 지워지지 않은 수들을 순회하며 각 수의 배수를 지우는 과정을 반복합니다. 이 때 지워지지 않은 수를 찾을 때 n이 아니라 sqrt(n) (i * i <= n)까지만 찾습니다.

Tips

i <= n이 아니라 i * i <= n까지만 확인하면 시간을 단축할 수 있습니다. 이는 작은 소수의 배수 제거 과정에서 이미 대부분의 합성수가 제거되기 때문입니다.

1/* ... */
2
3for (let i = 2; i * i <= n; i++) {
4  /* ... */
5}

3 ~ 4. i의 배수들을 모두 지울 때 2 x i 에서 시작하는 것이 아니라 i x i 부터 시작하면 계산하는데 시간을 단축할 수 있습니다. 이와 같은 과정을 반복하고 나면 결과적으로 남은 수들은 모두 소수가 됩니다.

Tips

i의 배수들을 모두 지울 때 i 보다 작은 배수들은 이미 이전 단계에서 제거되었기 때문에 j = i * i 부터 시작하면 계산하는데 시간을 단축할 수 있습니다.

1/* ... */
2
3for (let i = 2; i * i <= n; i++) {
4  // i가 소수인 경우, i의 배수를 모두 제거합니다.
5  if (isPrime[i]) {
6    for (let j = i * i; j <= n; j += i) {
7      isPrime[j] = false;
8    }
9  }
10}

최종 구현 결과는 다음과 같습니다.

1const n = 1000;
2const isPrime = new Uint8Array(n + 1).fill(true);
3isPrime[0] = false; // 0은 소수가 아닙니다.
4isPrime[1] = false; // 1은 소수가 아닙니다.
5
6for (let i = 2; i * i <= n; i++) {
7  // i가 소수인 경우, i의 배수를 모두 제거합니다.
8  if (isPrime[i]) {
9    for (let j = i * i; j <= n; j += i) {
10      isPrime[j] = false;
11    }
12  }
13}

3. Example

• 11690번: LCM(1, 2, ..., n)

  javascript

  1const path = process.platform === "linux" ? "/dev/stdin" : "input.txt";
  2const input = require("fs").readFileSync(path).toString();
  3
  4let answer = 1;
  5const n = Number(input); // 2 <= n <= 100_000_000
  6const isPrime = new Uint8Array(n + 1).fill(true);
  7isPrime[0] = false;
  8isPrime[1] = false;
  9
  10for (let i = 2; i * i <= n; i++) {
  11  if (isPrime[i]) {
  12    for (let j = i * i; j <= n; j += i) {
  13      isPrime[j] = false;
  14    }
  15  }
  16}
  17
  18for (let i = 2; i <= n; i++) {
  19  if (!isPrime[i]) {
  20    continue;
  21  }
  22
  23  let value = i;
  24
  25  while (true) {
  26    if (value * i > n) {
  27      answer *= value;
  28      answer %= Math.pow(2, 32);
  29      break;
  30    }
  31
  32    value *= i;
  33  }
  34}
  35
  36console.log(answer);

4. 참고 자료

• 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전
• 에라토스테네스의 체 - 나무위키