에라토스테네스의 체 (Sieve of Eratosthenes) - soo:bak

작성일 :

에라토스테네스의 체란?

에라토스테네스의 체(Sieve of Eratosthenes)는 특정 범위 내의 모든 소수를 효율적으로 찾는 알고리듬입니다.


문제 상황

100 이하의 모든 소수를 찾아야 한다면, 각 수마다 소수인지 판별하는 작업을 반복해야 합니다.

예를 들어, 97이 소수인지 확인하려면 2부터 √97 ≈ 9.8까지 나누어 떨어지는지 검사해야 합니다.

이런 방식으로 100개의 수를 모두 검사하면 매우 비효율적입니다.


에라토스테네스의 체는 이 문제를 다르게 접근합니다.

소수가 아닌 수들을 제거하는 방식으로, 한 번의 과정으로 범위 내 모든 소수를 찾아냅니다.

1
2
3
4
5
6
7
8
9

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

↓ 2의 배수 제거, 3의 배수 제거, 5의 배수 제거...

2  3     5     7        
11    13          17    19
   22 23       29


에라토스테네스의 체의 원리

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


1. 초기화

2부터 n까지의 모든 수를 소수 후보로 표시합니다.

0과 1은 소수가 아니므로 제외합니다.


2. 첫 번째 소수 선택

남아있는 수 중 가장 작은 수인 2를 소수로 확정합니다.


3. 배수 제거

선택한 소수의 배수를 모두 제거합니다.

예: 2의 배수 → 4, 6, 8, 10, 12, ... 제거


4. 다음 소수 선택

남아있는 수 중 가장 작은 수(3)를 다음 소수로 선택합니다.


5. 반복

√n에 도달할 때까지 3~4 단계를 반복합니다.


6. 결과

남아있는 모든 수가 소수입니다.


왜 √n까지만 확인하면 될까?

어떤 수 n이 합성수(소수가 아닌 수)라면, n = a × b로 표현할 수 있습니다.

이때 a와 b 중 적어도 하나는 √n 이하여야 합니다.


증명

만약 a > √n이고 b > √n이라면: \(a \times b > \sqrt{n} \times \sqrt{n} = n\)

이는 모순입니다. 따라서 a ≤ √n 또는 b ≤ √n이어야 합니다.


예시: n = 36

a b 관계
1 36 a < √36 = 6
2 18 a < √36 = 6
3 12 a < √36 = 6
4 9 a < √36 = 6
6 6 a = √36 = 6

√36 = 6이므로, 6 이하의 약수만 확인하면 모든 약수를 찾을 수 있습니다.


따라서 √n까지만 확인하면, 그보다 큰 약수는 자동으로 제거되므로 효율적입니다.

에라토스테네스의 체의 구현

에라토스테네스의 체는 간결한 코드로 구현할 수 있습니다.


기본 구현

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

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n = 100;  // n 이하의 모든 소수를 찾기
  
  vector<bool> isPrime(n + 1, true);  // 모든 수를 소수로 가정
  isPrime[0] = isPrime[1] = false;    // 0과 1은 소수가 아님
  
  // √n까지만 확인
  for (int i = 2; i * i <= n; i++) {
    if (isPrime[i]) {  // i가 소수라면
      // i의 배수를 모두 제거 (i*i부터 시작)
      for (int j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  
  // 소수 출력
  for (int i = 2; i <= n; i++) {
    if (isPrime[i]) {
      cout << i << " ";
    }
  }
  
  return 0;
}


핵심 최적화

  1. i * i부터 시작: i의 배수 중 i * i보다 작은 수들은 이미 이전 단계에서 제거되었습니다.
    • 예: 5의 배수를 제거할 때, 10(2×5), 15(3×5), 20(4×5)는 이미 제거됨
  2. √n까지만 확인: i * i > n이면 더 이상 제거할 배수가 없습니다.


소수 개수 세기

소수의 개수만 필요한 경우:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int countPrimes(int n) {
  if (n <= 2) return 0;
  
  vector<bool> isPrime(n, true);
  isPrime[0] = isPrime[1] = false;
  
  for (int i = 2; i * i < n; i++) {
    if (isPrime[i]) {
      for (int j = i * i; j < n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  
  int count = 0;
  for (int i = 2; i < n; i++) {
    if (isPrime[i]) count++;
  }
  
  return count;
}


소수 리스트 반환

소수를 벡터로 저장하는 경우:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

vector<int> getPrimes(int n) {
  vector<bool> isPrime(n + 1, true);
  isPrime[0] = isPrime[1] = false;
  
  for (int i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      for (int j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  
  vector<int> primes;
  for (int i = 2; i <= n; i++) {
    if (isPrime[i]) {
      primes.push_back(i);
    }
  }
  
  return primes;
}


시간 복잡도

에라토스테네스의 체의 시간 복잡도는 \(O(n \log \log n)\)입니다.


분석

각 소수 p에 대해 n/p개의 배수를 제거합니다.

전체 연산 횟수는: \(\frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \frac{n}{7} + \cdots = n \left( \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \cdots \right)\)

소수의 역수 합은 \(O(\log \log n)\)으로 수렴하므로, 전체 시간 복잡도는 \(O(n \log \log n)\)입니다.


비교

방법 시간 복잡도 설명
단순 판별 \(O(n \times \sqrt{n})\) 각 수마다 √n까지 확인
에라토스테네스의 체 \(O(n \log \log n)\) 배수 제거 방식


공간 복잡도: \(O(n)\)

n+1 크기의 불리언 배열을 사용합니다.


에라토스테네스의 체의 활용

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


범위 내 소수 찾기

  • 특정 범위의 모든 소수를 한 번에 구할 때
  • 소수의 개수를 세는 문제


소수 관련 전처리

  • 여러 쿼리에서 소수 판별이 필요한 경우
  • 소인수분해의 기초 자료 구축


약수 개수 계산

  • 에라토스테네스의 체를 변형하여 각 수의 약수 개수 계산


골드바흐의 추측

  • 짝수를 두 소수의 합으로 표현


실전 예제: 소수 구하기

문제: M 이상 N 이하의 소수를 모두 출력하세요.


제약 조건

  • 1 ≤ M ≤ N ≤ 1,000,000
  • N - M ≤ 100,000


접근법

N까지의 모든 소수를 에라토스테네스의 체로 구한 후, M 이상의 소수만 출력합니다.


구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int m, n;
  cin >> m >> n;
  
  // 에라토스테네스의 체
  vector<bool> isPrime(n + 1, true);
  isPrime[0] = isPrime[1] = false;
  
  for (int i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      for (int j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  
  // M 이상 N 이하의 소수 출력
  for (int i = m; i <= n; i++) {
    if (isPrime[i]) {
      cout << i << "\n";
    }
  }
  
  return 0;
}


시간 복잡도: \(O(n \log \log n)\)

에라토스테네스의 체를 사용하여 효율적으로 해결할 수 있습니다.


마무리

에라토스테네스의 체는 특정 범위 내의 모든 소수를 효율적으로 찾는 알고리듬입니다.


핵심 포인트

  • 배수 제거 방식으로 소수를 찾아내며, 시간 복잡도는 \(O(n \log \log n)\)
  • √n까지만 확인하면 되므로 효율적
  • 범위 내 모든 소수가 필요한 경우 가장 적합한 방법


소수를 하나씩 판별하는 것보다 범위 내 모든 소수를 한 번에 구하는 것이 효율적일 때 에라토스테네스의 체를 사용하면 좋습니다.

특히 여러 쿼리에서 소수 판별이 필요한 경우, 미리 에라토스테네스의 체로 전처리하면 각 쿼리를 \(O(1)\)에 처리할 수 있습니다.


관련 문제

이 블로그의 다른 글