[백준] java 4948 베르트랑 공준

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

문제

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

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

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

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

입력

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

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

풀이 과정

문제 입력에는 1 ≤ n ≤ 123,456라는 제한이 있다. 자연수 n에 제한이 걸려버리니 범위가 확 좁혀져서 난이도가 쉬워진 거 같다.

먼저, 자연수 중 1부터 123456까지 소수인 자연수만 기록해둔 뒤 n보다 크고 2n보다 작은 소수의 개수만 구해주면 될 거 같다.

소수 판별 메서드를 따로 작성하여 사용했다. 2부터 루트n까지 N을 나눠서 떨어지지 않으면 해당 수는 소수이다.

public static boolean isPrime(int N){
        if( 2 > N ) return false;
        for( int i = 2; i*i <= N; i++ ){
            if( N % i == 0) return false;
        }
        return true;
    }

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int count = 2;
        // 2n보다 작은 수이므로
        // 제한 범위 중 최대 숫자인 123456 * 2
        boolean[] numbers = new boolean[123457*2];
        while( 123457*2 >= count ){

            if( isPrime(count) ){
                numbers[count] = true;
            }
            count++;

        }

        while( true ){
		
            int N = Integer.parseInt(br.readLine());
            if( N == 0 )
                break;
            int doubleN = N*2;
            int primes = 0;
            // N보다 크고 2N보다 작은 소수의 개수
            for( int i = N+1; i <= doubleN; i++ ){

                if( numbers[i] )
                    primes++;

            }
            sb.append(primes).append("\n");

        }
        System.out.println(sb);
    }

출력 조건은 n보다 크고 2n보다 작은 소수의 개수이니 n의 최대값인 123456의 두배까지 소수를 구해줬다.

그리고 반복문

for( int i = N+1; i <= doubleN; i++ ){

        if( numbers[i] )
             primes++;

}

을 통해 N보다 크고 2N보다 작은 소수의 개수를 구해줄 수 있었다.