[백준 JAVA] 4948번 풀이 - 베르트랑 공준

package quiz;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * 4948번 풀이 - 베르트랑 공준
 * 베르트랑 공준은 임의의 자연수 n에 대하여,
 * n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
 * 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
 * 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19)
 *
 * 자연수 n이 주어졌을 때, n보다 크고 2n보다 작거나 같은 소수의 개수를 구하여라.
 *
**/
public class _4948 {

    public static void main(String[] args) throws Exception {

        //입력은 여러 개의 테스트 케이스로 이루어져 있다.
        //입력의 마지막은 0이다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){
            int n = Integer.parseInt(br.readLine());
            if (n == 0) break;

            //n < target <= 2n
            int[] arr = new int[(2*n) + 1];
            int count = 0;

            for ( int i = 2; i <= 2*n; i++ ) {
                arr[i] = i;
            }

            for ( int i = 2; i <= Math.sqrt(2*n); i++ ){
                if (arr[i] == 0) {continue;}

                //특정 수 배수 지우기.
                for ( int j = i + i; j <= 2*n; j+= i ){
                    arr[j] = 0;
                }
            }

            for (int i = n+1; i <= 2*n; i++) {
                if (arr[i] != 0) {
                    //System.out.println(arr[i]);
                    count++;
                }
            }

            System.out.println(count);

        }
    }
}

 

풀이

"에라토스테네스의 체" 를 이용해서 풀었다. 

배열은 2부터 2n까지. 

2n의 제곱근까지 수의 배수를 지워버리고, 출력만 n < target <= 2n 을 조회해서 뽑았다.