[백준] 9020번 : 골드바흐의 추측 _ JAVA ( 주석 설명 )

1번

→ '에라토스테네스의 채'를 이용한 골드바흐 파티션 구하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
    static boolean[] prime = new boolean[10001]; //소수 : false, 합성수 : true

    //전체 시간복잡도 : O(log(log(N))
    //전체 공간복잡도 : O(N)
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //버퍼에 입력을 받아 입력을 처리하는 변수이다.
        StringBuilder sb = new StringBuilder(); //출력값을 한번에 출력하기 위한 변수이다.

        int T = Integer.parseInt(br.readLine()); //테스트케이스 개수를 입력받는다.

        for(int i=0;i<T;++i){
            int num = Integer.parseInt(br.readLine()); //골드바흐 파티션을 출력하기 위한 짝수를 입력받는다.
            for(int j = 2;j<= Math.sqrt(num);++j){ //sqrt(num) 이후의 값은 불필요한 계산이다.
                for(int k = j*j;k<=num;k+=j){ //'에라토스테네스의 채' 원리로 각 제곱수들 합성수 체크
                    prime[k]=true;
                }
            }
            for(int a = num/2; a>=2; --a) { //두 소수의 차이가 가장 작은 것을 출력해야 하므로, 중앙수를 중심으로 체크
                if (!prime[a])//a와 num-a 모두 소수이면 출력한다.
                    if (!prime[num - a]) {
                        sb.append(a).append(' ');
                        sb.append(num - a).append('\n');
                        break; //다음 소수들의 합을 출력 안하게 하기 위한 break문이다.
                    }
            }
        }
        System.out.println(sb); //각 테스트케이스의 골드바흐 파티션을 출력한다.
    }
}