[JS][백준]4948_베르트랑 공준

문제 번호

4948번: 베르트랑 공준

 

 

알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

 

문제 풀이

 주어진 숫자(n)를 입력받아서 n+1 이상 2*n 이하의 소수의 개수를 구하면된다. n에 대한 소수여부를 판단할때 2이상 루트n 이하 로 나눠보면 판단할 수 있다.

 

전체코드

const input = require('fs').readFileSync('dev/stdin').toString().split('\n');

let TC = 0;

function sol() {
  let answer = '';
  
  while (1) {
    let n = +input[TC++];
    if (n === 0) break;

    let cnt = 0;
    for (let i = n + 1; i <= 2 * n; i++) {
      if (isPrime(i)) cnt++;
    }
    answer += `${cnt}\n`;
  }
  return answer;
}

function isPrime(n) {
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) return false;
  }
  return true;
}

console.log(sol().trim());

특이사항