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

문제

링크

---

코드

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

public class Main {

    static boolean[] primeNumber = new boolean[10001];

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

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int input = Integer.parseInt(br.readLine());
            int a = input / 2;
            int b = input / 2;

            while (true) {
                if (!primeNumber[a] && !primeNumber[b]) {
                    sb.append(a).append(" ").append(b).append("\n");
                    break;
                }
                a--;
                b++;
            }
        }
        br.close();
        System.out.print(sb);
    }

    static void searchPrimeNumber() {
        primeNumber[0] = primeNumber[1] = true;
        for (int i = 2; i <= Math.sqrt(primeNumber.length); i++) {
            if (primeNumber[i]) continue;
            for (int j = (i * i); j < primeNumber.length; j += i) {
                primeNumber[j] = true;
            }
        }
    }
}

---

리뷰

문제에 의하면 골드바흐 추측은 2보다 큰 수는 두 소수의 합으로 구할 수 있다는 것이다.

a + b = c 라고 가정하자 그러면 a + b가 어떤 수여도 합치면 c가 되어야한다. a가 1감소하면 b는 1증가해야 c가 된다.
이 점을 이용하여

a, b를 입력받은 값의 중앙값으로 두고 a는 감소하고 b는 증가시키며 두 수가 소수일 때가 문제에서 요구하는 (1) 두 소수의 합, (2) 여러 개의 조합이 가능한 경우 두 소수의 차이가 작은 것을 동시에 만족시킨다.