[백준 온라인 저지] 6588. 골드바흐의 추측

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

“4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.”

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

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

 

1. 입력

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

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

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

 

2. 출력

- 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다.

- 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다.

- 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

 

3. 예제

 

4. 코드

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 입력: 6 이상 백만 이하
        // 에라토스테네스의 체 구현
        boolean[] prime = new boolean[1000001]; // 소수라면 true
        Arrays.fill(prime, true); prime[1] = false;
        for(int i=2 ; i<=1000000 ; i++){
            if(prime[i]){
                for(int j=i*2 ; j<=1000000 ; j+=i)
                    prime[j] = false;
            }
        }
        // 입력에 대해서 골드바흐 추측이 맞는지 확인
        while(true){
            int n = Integer.valueOf(br.readLine()), a = -1, b = -1;
            if(n==0) break;
            for(int j=2 ; j<=n/2 ; j++)
                if(j<=n-j && prime[j] && prime[n-j]){
                    a = j; b = n-j; break;
                }
            if(a==-1)
                bw.write("Goldbach's conjecture is wrong.\n");
            else
                bw.write(n+" = "+a+" + "+b+"\n");
        }
        bw.flush(); bw.close();
    }
}

- 33484KB, 628ms

- j가 작은 수 부터 접근하기 때문에 j<=n-j는 빼도 상관 없다.