[백준 4948 - Node.js] 베르트랑 공준

문제 링크

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

풀이

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .slice(0, -1)
  .map(v => +v);

const prime = Array(123456 * 2 + 1).fill(true);
for (let i = 2; i <= 123456 * 2 + 1; i++) {
  if (!prime[i]) continue;
  for (let j = i * 2; j <= 123456 * 2 + 1; j += i) {
    prime[j] = false;
  }
}

const output = [];
for (const n of input) {
  let result = 0;
  for (let i = n + 1; i <= n * 2; i++) {
    if (prime[i]) result++;
  }
  output.push(result);
}
console.log(output.join('\n'));

문제에서 주어진 n의 최댓값이 123456이므로, 그 두 배까지의 소수를 모두 구해서 prime에 저장한다.

입력값들을 순회하면서 입력값 + 1부터 입력값 * 2까지의 소수의 개수를 세서 출력하였다.