에라토스테네스의 체

에라토스테네스의 체란?

에라토스테네스의 채(Sieve of Eratosthenes)는 소수 판별 알고리즘이다.
특정 범위(예: 1 ~ N) 안에 존재하는 모든 소수를 효율적으로 찾기 위해 고안되었다.

핵심 아이디어는

• 어떤 수가 소수라면, 그 수의 배수들은 모두 소수가 아니다.
• 따라서 소수를 하나씩 찾으면서, 그 소수의 배수를 지워 나가면 된다.

1.알고리즘 흐름

1. 2부터 N까지를 모두 후보로 둔다.
2. 아직 지워지지 않은 가장 작은 수 p를 찾는다. p는 소수다.
3. p의 배수들을 지운다. (보통 p*p부터 지운다)
4. p를 다음 수로 옮기며, p ≤ √N일 동안 반복한다.
5. 남은 수가 모두 소수다.

2. 동작 과정

예를 들어 N = 30 까지의 소수를 구한다고 하자.

1. 초기화
   2부터 30까지 모든 수를 후보로 둔다. (1은 소수가 아니므로 제외)
   후보: 2 3 4 5 6 7 8 9 10 11 12 ... 30
2. 2의 배수 제거
   가장 작은 소수 2를 찾는다.
   2는 소수이므로 그대로 두고, 2의 배수(4, 6, 8, 10...)를 지운다.
   남은 수: 2 3 X 5 X 7 X 9 X 11 ... 29
3. 3의 배수 제거
   아직 지워지지 않은 수 중 다음 수 3을 본다.
   3도 소수이므로 남기고, 3의 배수(6, 9, 12, ...)를 지운다.
   남은 수: 2 3 X 5 X 7 X X X 11 X 13 X X 17 X 19 ... 29
4. 5의 배수 제거
   다음 수 5를 본다.
   5도 소수이므로 남기고, 5의 배수(10, 15, 20, 25, 30)를 지운다.
   남은 수: 2 3 X 5 X 7 X X X 11 X 13 X X 17 X 19 X 23 X 29
5. √N까지만 반복
   여기서 중요한 점은, 배수를 지우는 작업은 √N까지만 수행하면 충분하다.
   (예: N=30 → √30 ≈ 5.47 → 5까지만 확인하면 된다.)
   왜냐하면 N보다 작은 수의 약수 중 큰 수는 반드시 작은 수와 짝을 이루기 때문이다.
   약수 둘 다 n보다 클 수 없기때문에 하나라도 n보다 작다면 앞선 과정에서 지워진다.

---

3. 최종 결과

남아있는 수들이 모두 소수다.
즉, 30 이하 소수는

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

---

4. 시간 복잡도

• 단순히 모든 수마다 나누어보는 방식은 O(N√N)이다.
• 하지만 에라토스테네스의 체는 O(N log log N) 이다.
• 매우 큰 N에 대해서도 빠르게 동작하기 때문에 널리 사용된다.

 

다음은 내가 백준 1929번을 이 알고리즘을 사용해서 푼 코드다.

https://www.acmicpc.net/problem/1929

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;

	cin >> n >> m;

	vector<int> arr(m + 1);

	for (int i = 2; i < m + 1; i++) {
		arr[i] = i;
	}

	for (int i = 2; i <= sqrt(m); i++) { #최댓값의 제곱근까지만
		if (arr[i] == 0) continue;
		for (int j = i + i; j <= m; j+=i) { #소수의 배수라면 0을 넣어 소수가 아님을 표시
			arr[j] = 0;
		}
	}
	for (int i = n; i < m+1;i++) { 
		if (arr[i] != 0) {
			cout << arr[i] << "\n";
		}
	}

	return 0;
}