[백준 | Javascript] 4948

기본 수학 2. 5단계
4948번. 베르트랑 공준

문제

4948번 문제 링크

solution

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map((x) => Number(x));

// 예제 입력 input.length = 8, 마지막 입력인 0 제외하고 반복하려면 0 ~ 6까지 반복해야함
// 따라서 input.length - 1 = 7 미만까지 반복
for(let i = 0; i < input.length - 1; i++){
  const num = input[i];
  let count = 0;
  
  // num이 1이라면 1,2 중 소수 개수 출력이므로 1이 나옴.
  if(num === 1){
    count++;
    console.log(count);
    
    // 다음 i로 넘어가면서 count 초기화
    continue;
  }
  
  // num이 1이 아닌 경우에 대하여 소수 개수 판별 진행
  // num보다 크고, 2*num보다 작거나 같은 수 중 소수를 찾는게 목표
  // 따라서, 판별해야할 범위 j는 num+1 ~ 2*num
  // j가 소수인지 판별해서 count를 증가시킨 후 마지막에 count를 출력하면
  // num+1 ~ 2*num 범위에서의 소수 개수 출력 가능
  outer: for(let j = num + 1; j <= 2*num; j++){
    // j에 대하여 소수 판별 진행
    inner: for(let k = 2; k*k <= j; k++){
      // k로 나누어 떨어지면 소수가 아니므로 outer 반복문 continue
      if(j % k === 0){
        continue outer;
      }
    }
    
    // inner 반복문을 통과하면 소수이므로 count 증가
    count++;
  }
  
  // num에 대한 최종 count 출력
  console.log(count);
}

해설

평범한 방법으로도 시간 초과 문제없이 통과할 수 있었지만, 시간 제한 조건이 있었다면 에라토스테네스의 체를 사용해야 할 것 같다.
에라토스테네스의 체를 사용했던 다른 문제