백준 4948번 베르트랑 공준

 

출처 링크:

https://www.acmicpc.net/problem/4948

 

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

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

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

 

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

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

(범위: 1 ≤ n ≤ 123,456)

 

풀이

 

let input = [1, 10, 13, 100, 1000, 10000, 100000, 0]

//console.log(input);
solution(input);

function solution(A) {
  for (let i = 0; i < A.length; i++) {
    // 입력값을 받는 for문
    if (A[i] === 0) {
      // 0이라면 for문을 끝낸다.
      break;
    }
    //console.log(A[i]);
    let decimal = 0; // 소수 숫자세기위한 변수
    for (let j = A[i] + 1; j <= A[i] * 2; j++) {
      // 자연수 n보다 크고 2n보다 작거나 같은 조건입니다.
      //console.log(j);

      if ((j === 2) | (j === 3) | (j === 5) | (j === 7)) {
        // 2,3,5,7은 소수입니다.
        decimal++;
      } else if (
        // 에라토스테네스의 체를 이용했습니다. 소수가 아닌 아이들을 대량으로 걸러줍니다.
        (j % 2 === 0) |
        (j % 3 === 0) |
        (j % 5 === 0) |
        (j % 7 === 0)
      ) {
        continue;
      } else {
        let count = 0;
        /* k로 j를 나누었을 때 정수가 된다면 소수가 아닙니다.
        어떤 수 j의 약수들의 중심 값은 루트 j 입니다. (약수가 존재한다면 그 약수와
        쌍을 이루는 다른 약수가 있기 마련 입니다.
        예를 들어 6의 약수가 1 2 3 6 이기에 1은 6과, 2는 3과 쌍을 이루는 것 처럼 말입니다.)
        루트 j는 그 약수들의 중간 값입니다. 약수가 존재하는 수에서 중간 값 보다
        작은 수가 1이 아니라 다른수가 있다는 것은 그k라는 수가 소수가 아니라는 뜻입니다.
        루트 j의 이러한 특성을 활용하면 시간 복잡도를 O(루트j)까지 줄일 수 있습니다.)
        */
        for (let k = 2; k <= Math.sqrt(j); k++) {
          if (Number.isInteger(j / k)) {
            count++;
          }
        }
        if (count === 0) {
          //count가 0이라면 소수입니다.
          decimal++;
        }
      }
    }
    console.log(decimal);
  }
}

 

 

소수들을 대량으로 걸러내는 작업을 위해 사용한 개념이 '에라토스테네스의 체'이다.

에라토스테네스의 체 설명

https://velog.io/@max9106/Algorithm-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

 

 

참고자료

 

isInteger()

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/isInteger

 

비트연산자 | (OR)

http://prof.dongju.ac.kr/syhong/public_html/teaching/c/c04.htm#%EC%82%B0%EC%88%A0%20%EC%97%B0%EC%82%B0%EC%9E%90(arithmetic%20operator)