[백준 1929번] 소수 구하기 - JavaScript

 

이 문제는 두 수를 받아 그 사이의 수들 중 소수를 출력하는 문제이다.

일반적인 소수 판별 기법을 사용한다면 메모리 제한 때문에 정답이 나오지 않는다.

 

따라서 우리는 에라토스테네스의 체(Sieve of Eratosthenes)를 사용해야 한다.

 

 

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

에라토스테네스의 체는 특정 범위 내에서 모든 소수를 빠르게 찾는 알고리즘
이 방법은 배수를 제거하는 방식으로 소수를 판별하며, **O(N log log N)**의 시간 복잡도를 가진다.

 

 

• 1부터 N까지의 숫자를 담은 배열을 생성하고, 모든 숫자를 소수라고 가정
  • 예: N = 10 → [true, true, true, true, true, true, true, true, true, true, true]
  • true는 해당 숫자가 소수임을 의미함.
• 2부터 시작하여 남아있는 가장 작은 수를 소수로 확정
  • 2는 소수이므로 2의 배수를 모두 제거
  • 3은 소수이므로 3의 배수를 모두 제거
  • 4는 이미 제거되었으므로 건너뜀.
• 제거 과정 반복 (√N까지만 검사하면 충분함)
  • 특정 숫자의 배수를 지우는 것은 그 숫자가 소수일 경우에만 실행
  • 예를 들어, 10까지 소수를 찾을 때 √10 = 3.16 → 2와 3까지만 검사하면 됨.
• 배수 제거가 끝난 후 남아있는 수가 소수

 

예시는 GPT를 참고한다.

 

아무튼 위와 같은 방식으로 루트(크기)만큼 배수를 삭제하면 남는 수가 해당 범위 내의 소수가 되는 것이다.

 

 

위 이론을 바탕으로 작성한 소스 코드는 아래와 같다.

 

소스 코드

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

const M = Number(input[0]);
const N = Number(input[1]);

const isPrime = Array(N + 1).fill(true);
isPrime[0] = isPrime[1] = false;

for (let i = 2; i * i <= N; i++) {
	if (isPrime[i]) {
		for (let j = i * i; j <= N; j += i) {
			isPrime[j] = false;
		}
	}
}

const result = [];
for (let i = M; i <= N; i++) {
	if (isPrime[i]) {
		result.push(i);
	}
}

console.log(result.join('\n'));