[Baekjoon] 9020번: 골드바흐의 추측

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

문제 설명

골드바흐의 추측은 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들어 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

풀이 방법

문제에서 고려해야 할 사항은 두 가지다.

 

1. 소수 구하기
2. 골드바흐 파티션이 여러 가지인 경우 두 소수의 차이가 가장 작은 것을 출력하기

먼저 1번은 에라토스테네스의 체를 활용해서 해결한다. 간략히 설명하자면 \(O(n \log(\log n))\) 의 시간복잡도를 가지는 소수를 구하는 효율적인 방법이다. 이를 이용해 boolean 배열을 만들어놓고 소수인 인덱스의 값은 false로 남겨놓는다.

 

문제는 2번이다. 주어진 짝수에서 어떻게 차이가 가장 작은 것을 구해내야 할까? 바로 짝수의 절반부터 포인터 변수를 활용해서 찾아가는 것이다. 왼쪽 포인터 변수는 p, 오른쪽 포인터 변수는 q라고 둔다. 그리고 두 수가 소수인지는 만들어 둔 boolean 배열로 확인한다. 두 수가 소수인 경우 두 수를 더하면 그것이 차이가 가장 적은 골드바흐 파티션이 된다. 아니라면 p는 왼쪽으로, q는 오른쪽으로 이동하면서 계속 확인하다가 두 수가 소수인 경우에 그 파티션을 출력하면 된다.

import java.io.*;

class Main {
    static final int RANGE = 10_000;
    static boolean[] sieve = new boolean[RANGE + 1];

    static {
        sieve[0] = sieve[1] = true;

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

            for (int P = i * i; P < sieve.length; P += i) {
                sieve[P] = true;
            }
        }
    }

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

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

        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());

            int p = n / 2;
            int q = n / 2;

            while (true) {
                if (sieve[p] == false && sieve[q] == false) {
                    sb.append(p + " " + q).append("\n");
                    break;
                }
                p--;
                q++;
            }
        }

        System.out.print(sb);
    }
}