[백준] 17103번 골드바흐 파티션 JAVA

 

골드바흐의 추측 응용편

거의 비슷한데 같은 수의 조합도 카운트 해주는 부분만 신경 쓰면 쉽게 풀 수 있다.

 

import java.io.*;

public class Main {
    public static final int MAX = 1000000;
    public static void main(String args[]) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        boolean[] isPrime = new boolean[MAX];
//		  배열 초기화
        for(int i=0; i<MAX; i++){
            isPrime[i] = true;
        }
//        소수 배열을 만든다
        for(int i=2; i<MAX/2; i++){
            for(int k=i *2; k<MAX; k+=i){
                if(!isPrime[k]) continue;
                isPrime[k] = false;
            }
        }
        
        int inputNum = Integer.parseInt(reader.readLine());
        
        for(int k=0; k<inputNum; k++){
            int input = Integer.parseInt(reader.readLine());
            int cnt = 0;
            int limit = input/2;
//          입력은 어짜피 짝수, 같은 수의 페어가 답이 될 수 있음으로 <=으로 루프를 돌린다.
            for(int i=2; i<=limit; i++){
                if(isPrime[i] && isPrime[input-i]){
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
        reader.close();
    }
}