에라토스테네스의 체

문제

언어

  • JavaScript

순서도

  1. 2부터 N까지 모든 정수를 적는다.
  2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
  3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
  4. 지울 때, 지운 수의 횟수를 세고, 횟수가 k번에 도달하면 지운 수를 출력한다.
  5. 아직 횟수가 k번에 도달하지 못했고, 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

문제 풀이 step 1

  • 실제 에라토스테네스의 체에서는 2번 단계에서 아직 지우지 않은 수 P는 소수이므로 P는 지우지 않습니다.
  • 하지만, 본 문제에서는 P를 지워야한다는 점이 차이점입니다.
  • 문제에서 주어진 알고리즘대로 구현하면 되는 문제로 중간에 지운 수의 횟수를 세고, 그 수를 k와 비교하는 로직만 추가하면 되는 문제입니다.
  • 추가 설명은 주석에 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const [n, k] = input[0].split(" ").map(Number);
	// 1. 배열 생성을 통해서 2 ~ N 가지 모든 정수 적기
	const arr = Array.from({length: n + 1}, () => false);

	let cnt = 0;
	for (let i = 2; i < n + 1; i++) {
		// 이미 지운 수라면 넘어가고
		if (arr[i] === true) continue;

		// 아직 지우지 않은 수 중에서 가장 작은 수의 배수를 모두 지우기
		for (let j = i; j < n + 1; j += i) {
			// 이미 지운 수라면 넘어가고
			if (arr[j] === true) continue;

			// 지우지 않았다면 지우고, 횟수 세기
			arr[j] = true;
			cnt += 1;

			// 지운 수의 횟수가 k 에 도달했다면 지운 수를 출력
			if (cnt === k) return j;
		}
	}
};

console.log(solution(input));