[Algorithm/JS] 백준 4948번 베르트랑 공준

🔗 문제 바로가기 (opens new window)

Question

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

Input

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

Output

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

Limit

• 1 ≤ n ≤ 123,456

Example

Input 1

1
10
13
100
1000
10000
100000
0

Output 1

1
4
3
21
135
1033
8392

Solution

Solution 1 (시간초과)

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

input.map((n) => {
  let count = 0;
  for (let i = n + 1; i <= 2 * n; i++) {
    let decimal = true;
    if (i <= 1) continue;
    for (let k = 2; k < i; k++) {
      if (i % k === 0) {
        decimal = false;
        break;
      }
    }
    if (decimal) count++;
  }
  if (n !== 0) console.log(count);
});

풀이는 2581 소수 (opens new window) 와 유사하다. 위 코드 실행 결과 출력값은 예시와 동일하다. 분명 시간 초과 라는 결과를 낼 것이라고 풀면서도, 출력하면서도 느꼈다. 역시 시간초과다. 😅 해결 방법을 찾아보니 에라토스테네스의 체를 활용할 수 있다고 한다.

Solution 2 (성공)

에라토스테네스의 체 (opens new window) 방법은 링크된 문서에서 자세히 설명한다.

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

input.map((n) => {
  if (n === 0) return; // *
  const num = n; // (1) 각 입력값(n) 값
  const max = num * 2; // (1) 입력값의 두배 (2n)
  const isPrime = Array(max + 1).fill(true); // (2)
  isPrime[0] = isPrime[1] = false; // (2) 0과 1은 소수가 아니다.

  for (let i = 2; i <= Math.ceil(Math.sqrt(max)); i++) {
    // (3)
    if (isPrime[i]) {
      // (4)
      let t = 2; // (5)
      while (i * t <= max) {
        isPrime[i * t] = false;
        t++;
      }
    }
  }

  let results = []; // (6)
  for (let i = num + 1; i <= max; i++) {
    // (7)
    if (isPrime[i]) results.push(i);
  }
  console.log(results.length);
});

💡 먼저 입력값이 0 일 땐 아무것도 반환하지 않아야 하기때문에, map 함수를 실행하자마자 해당 입력 값이 0 이라면 그대로 return 을 사용하여 빠져나가도록 작성했다.

1. 각 입력값을 num, 입력값의 두배가 되는 값을 max라고 정했다.

2. isPrime 배열은 max + 1 만큼의 공간을 갖고 모든 공간을 true로 채운다. 0과 1은 소수가 아니기 때문에 false 를 할당한다.

3. 2부터 max 의 제곱근 만큼만 순환할 반복문을 작성했다.

   max 까지 모든 수를 순환하면 불필요한 반복으로 인해 시간이 오래걸려 시간이 초과될 것이다.

4. isPrime 배열의 i 번째 인덱스가 true 라면 조건문을 실행하는데

5. 에라토스테네스의 체 방법에 의하면 2를 제외한 2의 배수를 제거하고, 3을 제외한 3의 배수를 제거한다. 그리고 4, 5, 6 ... 순차적으로 n의 배수를 제거하면 최종적으로 남는 수는 소수가 된다.

   이를 코드에 적용해, t 라는 변수를 생성하고 2로 초기화했다. i * t (t의 배수) 가 max보다 작거나 같을 때까지 반복하는 while 문을 실행하여 해당하는 인덱스의 값을 false 처리해준고, 다음 수의 배수를 검사하기 위해 t의 값은 증감연산자를 사용한다.

6. 소수만 걸러낼 배열 변수 results 를 생성했다.

7. 문제에서 출력 값은 ‘n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력’ 한다고 했기 때문에 i 의 초기 값은 num + 1이며, max 값보다 작거나 같은 수 만큼 반복해 true 인 값만 results 배열에 push 한다.

8. 마지막으로 results 배열의 길이로 해당 입력값의에 따른 소수의 개수를 출력한다!

   성공!