문제 바로가기

4948 베르트랑 공준

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

Solution 2 (성공)

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

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 배열의 길이로 해당 입력값의에 따른 소수의 개수를 출력한다!

    성공!