[BaekJoon-6588] 골드바흐의 추측

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 “Goldbach’s conjecture is wrong.”을 출력한다.

예제 입력 1

예제 출력 1

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

풀이방법

에라토스테네스의 체로 합성수 표시 배열을 만든다. 이 배열에서 composite[x]가 false인 2 이상의 x가 소수다. 후보 a와 n−a가 모두 소수이면 합이 n인 쌍을 찾은 것이다. a를 작은 홀수부터 검사하면 b−a가 가장 큰 쌍에서 멈출 수 있다.

가장 작은 첫 소수부터 시도하기

짝수 n을 a+b로 나타낼 때 a가 작을수록 b−a=n−2a가 커진다. 따라서 홀수 소수 후보 a를 3부터 증가시키며 처음으로 n−a도 소수인 쌍을 찾으면 출력 조건을 만족한다. n=42라면 3+39는 39가 합성수라 실패하고 5+37이 첫 성공이다. n=6은 3+3이므로 두 소수가 같아도 된다.

많은 테스트 케이스마다 소수를 다시 판정하지 않도록 1,000,000까지 에라토스테네스의 체를 한 번 만든다. composite[x]가 true면 합성수다. 각 소수 p의 배수는 p²부터 표시해도 앞의 작은 소수에서 이미 지운 값은 빠지지 않는다. 찾은 쌍은 StringBuilder에 쌓아 한 번에 출력한다. 끝의 0은 종료 표시라 처리하지 않는다.

이 문제는 무한한 모든 짝수에 관한 추측을 증명하는 것이 아니라 주어진 유한 범위의 입력에 대해 쌍을 찾는 프로그램이다. 쌍이 없다면 정해진 영문 문장을 줄바꿈과 함께 출력한다. 체는 O(L log log L) 시간과 O(L) 공간(L=1,000,000)이고, 각 질문의 후보 탐색은 최악 O(n)이지만 첫 성공에서 멈춘다. 기존 조건식에는 같은 소수 판정이 두 번 있었고 실패 출력 뒤의 줄바꿈이 빠져 있었다.

소스코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        final int limit = 1_000_000;
        boolean[] composite = new boolean[limit + 1];
        for (int prime = 2; prime * prime <= limit; prime++) {
            if (composite[prime]) continue;
            for (int multiple = prime * prime; multiple <= limit; multiple += prime) {
                composite[multiple] = true;
            }
        }

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        while (true) {
            int n = Integer.parseInt(in.readLine());
            if (n == 0) break;
            boolean found = false;
            for (int a = 3; a <= n / 2; a += 2) {
                int b = n - a;
                if (!composite[a] && !composite[b]) {
                    out.append(n).append(" = ").append(a).append(" + ").append(b).append('\n');
                    found = true;
                    break;
                }
            }
            if (!found) out.append("Goldbach's conjecture is wrong.\n");
        }
        System.out.print(out);
    }
}