에라토스테네스의 체란?

에라토스테네스의 체(Sieve of Eratosthenes)는 고대 그리스의 수학자 에라토스테네스가 고안한 소수를 구하는 알고리즘이다.

• 이 알고리즘은 체를 이용해 가루나 액체를 분리하는 과정과 비슷해서 ‘체’라고 불린다.
• 이 방법은 주어진 숫자 범위 내에서 소수만을 걸러낼 수 있다.
• 이 방법은 소수를 찾기보다 소수의 배수를 반복적으로 제거하여 남아있는 숫자가 모두 소수임을 확인한다.

※ 소수 : 1과 자기 자신만을 약수로 가지는 자연수 ex. 2, 3, 5, 7

---

에라토스테네스의 체 알고리즘

1. 초기화 : 2부터 시작하여 n까지의 모든 정수를 나열한다.
2. 제거 : 현재 숫자의 배수를 제거한다. 이때, 현재 숫자는 소수이므로 제거하지 않는다.
3. 반복 : 제거 과정을 n의 제곱근까지만 반복한다.
4. 결과 확인 : 제거되지 않은 숫자는 모두 소수다.

예시 (n = 20)

1. 2부터 20까지의 모든 정수를 나열

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

1. 2의 배수 제거

2	3		5
7		9		11
	13		15
17		19		21

1. 3의 배수 제거

2	3		5
7				11
	13
17		19

1. 제거되지 않은 숫자인 2, 3, 5, 7, 11, 13, 17, 19 는 모두 소수이다.

---

JavaScript로 구현

function sieveOfEratosthenes(n) {
	// 2~n까지의 모든 숫자를 소수(true)로 초기화
	const isPrime = Array(n + 1).fill(true).fill(false,0,2); 
	
	for (let i = 2; i <= n; i++) {
		if (isPrime[i]) {
			// i의 배수는 소수가 아니므로 false로 변경
			for (let j = i * i; j <= n; j += i) {
				isPrime[j] = false; 
			}
		}
	}
	
	return isPrime
			.map((prime, index) => (prime ? index : null))
			.filter(Number.isInteger);
}

console.log(sieveOfEratosthenes(20));
// 출력: [2, 3, 5, 7, 11, 13, 17, 19]

---

에라토스테네스의 체의 복잡도

• 시간 복잡도 : O(n * log(log n))
• 공간 복잡도 : O(n)

---

백준 - 에라토스테네스의 체

문제

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)

출력

첫째 줄에 K번째 지워진 수를 출력한다.

const fs = require('fs');
const input = fs.readFileSync('dev/stdin').toString().trim();
const [N, K] = input.split(' ').map(Number);

let count = 0;

const isPrime = Array(N + 1)
	.fill(true)
	.fill(false, 0, 2);

outer: for (let i = 2; i <= N; i++) {
	if (isPrime[i]) {
		for (let j = i; j <= N; j += i) {
			if (!isPrime[j]) continue; // 이미 지운 숫자는 건너뜀
			isPrime[j] = false;
			count += 1;
			if (count === K) {
				console.log(j);
				break outer;
			}
		}
	}
}

// 입력
10 7

// 출력
9