[백준 온라인 저지] 17103. 골드바흐 파티션

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 두 소수의 순서만 다른 것은 같은 파티션이다.

 

1. 입력

- 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

 

2. 출력

- 각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

 

3. 예제

 

4. 코드

import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.valueOf(br.readLine());
        for(int i=0 ; i<t ; i++){
            int n = Integer.valueOf(br.readLine());
            boolean[] notprime = new boolean[n+1]; // 소수라면 false
            eratosthenes(notprime);
            int count = 0;
            for(int j=2 ; j<=n/2 ; j++){
                if(j<=n-j && !notprime[j] && !notprime[n-j])
                    count++;
            }
            bw.write(count+"\n");
        }
        bw.flush(); bw.close();
    }
    
    static void eratosthenes(boolean[] d){
        for(int i=2 ; i<d.length ; i++){
            if(d[i]==false){
                for(int j=i*2 ; j<d.length ; j+=i)
                    d[j] = true;
            }
        }
    }
}

- 72852KB, 608ms