[java] 백준 알고리즘 9020번 골드바흐의 추측 풀이

에라토스테네스의 체를 활용해서 푸는 문제이다.

에라토스테네스는 소수의 배수를 통해서 소수가 아닌 수를 삭제해나가는 것이다.

그리고 삭제되지 않은 수가 소수라는 뜻!

에라토스테네스 체로 먼저 소수를 찾아두고,

입력된 숫자를 반으로 나눈 뒤,

출력될 왼쪽의 수는 -- 하면서 출력될 오른쪽의 수는 ++해준다.

동시에 소수가 나오면 골드바흐의 추측 조건에 만족한다. 그러면 break;

* 풀이 소스

 
public class Baekjoon9020{
 
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
    /* 최대 입력값 10000을 넣어본 결과 더해지는 값 중 큰 값이 5081로 나온다. */
        boolean[] findingPrimeNum = new boolean[5082]; 
        Arrays.fill(findingPrimeNum, true);
        findingPrimeNum[0] = false;
        findingPrimeNum[1] = false;
        
    /* 에라토스테네스의 체 구현 */
        for(int i=2; i*i<=5081; i++) {
            
            if(findingPrimeNum[i]) {
                for(int j=i*i; j<=5081; j+=i) {
                    findingPrimeNum[j] = false;
                }
            }
        }
        for(int t=0; t<T; t++) {
            st = new StringTokenizer(br.readLine());
            int givenNum = Integer.parseInt(st.nextToken());
            int firstPartitian = givenNum/2;
            int secondPartitian = givenNum/2;
            
            while(true) {
                
                /* 골드바흐의 추측 조건에 만족하면 break */
                if(findingPrimeNum[firstPartitian] && findingPrimeNum[secondPartitian]) { 
                    break;
                }
                firstPartitian--;
                secondPartitian++;
            }
            bw.write(firstPartitian +" "+ secondPartitian+"\n");
        }
        bw.flush();
    }
 
}