[백준 문제풀이] 4948 베르트랑 공준

4948 베르트랑 공준

소수를 구하는 문제이다.
이전 문제풀이에서도 비슷한 문제가 있었는데, 그 때는 그냥 넘겼던 에라토스테네스의 체로 구현해보았다.

// 백준 4948 베르트랑 공준

const fs = require('fs');
const input = fs.readFileSync("input.txt").toString().trim().split("\n");

function isPrime(x) {
  let arr = Array(x+1).fill(true);
  let cnt = 0;
  
  arr[0] = false;
  arr[1] = false;

  for (let i=2; i*i<=x; i++) {
    if (arr[i]) { 
      for (let j=i*i; j<=x; j+=i) {
        arr[j] = false; // 소수가 아닌 경우
      }
    }
  } 
  // 소수는 인덱스 값이 true인 배열 arr
  for (let i=0; i<=x; i++) {
    if (arr[i]) {
      cnt++;
    }
  }
  return cnt;
}

for (let i=0; i<input.length; i++) {
  let n = Number(input[i]);
  let cnt = 0;

  // 종료문
  if (!n) break;

  console.log(isPrime(2*n)-isPrime(n));
}

소수인 숫자의 인덱스에 true를 가지는 배열 arr 를 만드는 함수 isPrime
소수의 개수를 반환하도록 하였다.

개수만 구해도 됐을 것 같은데 어렵게만 생각하다 보니 오히려 단순한 풀이를 하지 못했다😓