Algorithm/BaeKJoon

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

JaeKwan 2022. 1. 3. 14:08

문제 번호

 

4948번: 베르트랑 공준

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼

www.acmicpc.net

 

 

알고리즘 분류

 

문제 풀이

 주어진 숫자(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());

특이사항