# 백준 4948번 베르트랑 공준 (javascript, node.js)

백준 4948번 베르트랑 공준 (javascript, node.js)

문제

• 백준 4948번 다음 소수 문제 보러 가기
• 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
• 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
• 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)
• 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

4948번: 베르트랑 공준

---

입력

• 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.
• 입력의 마지막에는 0이 주어진다.

출력

• 각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

---

예제입력 1

1
10
13
100
1000
10000
100000
0

예제출력 1

1
4
3
21
135
1033
8392

문제풀이

• 문제는 길지만 결국 n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 문제
• 문제는 어렵지 않지만 문제를 풀 때 제대로 안 보고 풀어서 틀렸음
• n보다 큰 소수를 구하여야해서 반복문에 n + 1 해줌

// 4948번 베르트랑 공준 구하기

// n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 구현

// n과 2n 사이의 모든 수를 소수판별기를 통해 실행해서 나온 소수들은 배열에 저장

// 문제 풀면서 주어진 문제를 제대로 못봐서 n보다 크고, 작거나 같은 소수라고하였는데
// n을 포함한(n에 +1을 안함) 소수를 구하여 문제를 틀림

const fs = require("fs");
const file = process.platform === "linux" ? "dev/stdin" : "./text.txt";
const input = fs.readFileSync(file).toString().trim().split("\n");

// 소수 판별식
function isPrime(num) {
  if (num < 2) {
    return false;
  }

  for (let i = 2; i <= Math.floor(Math.sqrt(num)); i++) {
    if (num % i === 0) {
      // 한 번이라도 나누어 졌으니 소수가 아니므로 return false
      return false;
    }
  }
  // 나눠진 수가 없다면 해당 수는 소수이므로 return true
  return true;
}

//입력값 마지막 0 을 없애기 위해 input.length-1
for (i = 0; i < input.length - 1; i++) {
  const n = parseInt(input[i]);
  let result = [];

  // 문제에 n보다 크고 2n보다 작거나 같은 소소의 개수라고 하여
  // n에 +1 해줌
  for (j = n + 1; j <= 2 * n; j++) {
    if (isPrime(j)) {
      result.push(j);
    }
  }
  console.log(result.length);
}