[백준 / Node.js] 1929번: 소수 구하기(에라토스테네스의 체)📌

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

입력

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

출력

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

예제 입력1

3 16

예제 출력1

3
5
7
11
13

이번 문제처럼 1,000,000까지의 큰 범위가 주어졌을 때는 에라토스테네스의 체 방식을 사용하는 것이 효율적이다.

에라토스테네스의 체
https://gurtn.tistory.com/103

답(에라토스테네스의 체 안씀)

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [M, N] = input[0].split(" ").map((item) => +item);

function isPrime(num) {
  if (num === 1) return;
  for (let j = 2; j <= Math.sqrt(num); j++) {
    if (num % j === 0) return;
  }
  return console.log(num);
}

for (let i = M; i <= N; i++) {
  isPrime(i);
}

에라토스테네스의 체 (확실히 빠르다)

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, m] = input[0].split(" ").map((item) => +item);

// 에라토스테네스의 체
const prime = { 1: true };

for (let i = 2; i <= Math.sqrt(m); i++) {
  if (prime[i]) continue;
  for (let j = i ** 2; j <= m; j += i) {
    prime[j] = true;
  }
}
const results = [];

for (let i = n; i <= m; i++) {
  if (!prime[i]) results.push(i);
}
console.log(results.join("\n"));