백준<1929> - 소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

---

문제 접근

에라토스테네스의 체, 소수, 제곱근

소수란?

1과 자기 자신만 약수로 가진 수.
2 or 3의 배수가 아니다 가 소수로 귀결되진 않는다.


예시: 5*5 = 25 | 5*7 = 35 | 7*7 = 49
예시속에서 2 또는 3의 배수가 아닌 5와 7 등의 소수끼리 곱했지만, 결과로 합성수가 나오는 것을 확인할 수 있음.

제곱근 개념은 왜 필요한가?

모든 합성수는 루트n 이하의 약수를 갖는다.
루트n보다 커지는 시점이 오면, 삭제할 게 없는 것으로 판별가능.
n이하의 모든 합성수는 루트n 이하의 어떤 수의 배수로 이미 지워져야 함

• 1은 소수가 아니다. 제거해야함
• 그 다음 2의 배수 모두 제거
• 그 다음 3의 배수 모두 제거
• 그 다음 5의 배수 모두 제거...

정답

const fs = require("fs");
const [M, N] = fs.readFileSync(0, "utf8").trim().split(/\s+/).map(Number);

const isPrime = new Uint8Array(N + 1).fill(1);
// 0과 1은 소수가 아니므로 초기화
if (N >= 0) isPrime[0] = 0;
if (N >= 1) isPrime[1] = 0;

// 에라토스테네스의 체
for (let p = 2; p * p <= N; p++) {
  if (isPrime[p]) {
    for (let k = p * p; k <= N; k += p) isPrime[k] = 0;
  }
}

// 한 줄에 하나씩 출력 (버퍼에 모아 한 번에)
// Math .max(M, 2)부터 N까지 소수를 출력
const out = [];
for (let i = Math.max(M, 2); i <= N; i++) {
  if (isPrime[i]) out.push(String(i));
}
console.log(out.join("\n"));