[백준] 9020 - 골드바흐의 추측 (Java)

[백준] 9020번 : 골드바흐의 추측 - JAVA [자바]

*해당 포스팅은 상단에 링크된 포스팅을 바탕으로 개인 공부 목적을 위해 작성되었으므로 자세한 내용은 위 링크를 확인해 주시기 바랍니다.

---

선생님(모르는 제자가 하나 생기신)이 저번에 알려주신 골드바흐의 추측이 문제로 나왔다. 댓글에 나랑 비슷하게 생각하신 분이 계셨다.

 

진짜 나는 여기서 한 번 더 배워간다. 선생님은 천재다.

 

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

public class Main {

    /**
     * 골드바흐의 추측
     * 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다.
     *
     * 골드바흐 파티션
     * 짝수를 두 소수의 합으로 나타내는 표현
     * 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, ...
     */

    public static boolean[] prime = new boolean[10001];

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

        get_prime();

        int N = Integer.parseInt(br.readLine());

        while (N-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int first = n / 2;
            int second = n / 2;

            while (true) {
                if(!(prime[first]) && !(prime[second])) {
                    sb.append(first).append(" ").append(second).append("\n");
                    break;
                }
                first--;
                second++;
            }
        }
        System.out.println(sb);

    }

    public static void get_prime() {
        prime[0] = prime[1] = true;

        for (int i = 2; i <= Math.sqrt(prime.length); i++) {
            if (prime[i]) continue;
            for (int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}

 

에라토스테네스의 체 알고리즘을 자바로 구현하는 게 이제는 손에 익었다. 문제 하나 풀 때마다 제대로 이해하고 넘어가는 게 정말 중요한 거구나를 확실히 느꼈다.