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."을 출력한다.

풀이

주어진 짝수를 두홀수의 합으로 나타내는 문제이다.
n = a + b 형태로 출력할때, b - a가 가장 큰수를 출력하라고 하였으므로 n을 1씩 빼가면서 소수인 경우를 찾고, 소수라면 n - b = a 를 통해 찾은 a도 소수인지 확인해야 한다.

코드

첫번째 시도

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

public class 골드바흐의추측 {  

    public static StringBuilder sb = new StringBuilder();  

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

        while (true){  
            int n = Integer.parseInt(br.readLine());  
            if(n == 0) break;  
            goldbach(n);  
        }  

        System.out.println(sb);  
        br.close();  
    }  

    private static void goldbach(int n) {  

        for(int i=n; i>0; i--){  
            if(isPrime(i)){ // i가 소수인지 확인  
                int temp = n - i;  

                if(isPrime(temp)){ // n - i 가 소수인지 확인  
                    sb.append(n).append(" = ").append(temp).append(" + ").append(i).append("\n"); // n = temp + i 형태.  
                    return; //찾으면 골드바흐추측을 끝내준다.  
                }  
            }  
        }  
        sb.append("Goldbach's conjecture is wrong.");  
        return;  
    }  

    private static boolean isPrime(int index) {  
        if (index < 2) return false; // 2보다 작으면 소수가 아님.  

        for (int i = 2; i * i <= index; i++) { //루트N 만 확인하면 되니까 i*i로 푸는것.  
            if (index % i == 0) {  
                return false;  
            }  
        }  
        return true;  
    }  

}

실패!
정상적으로 동작하는것같아서 제출해보니 시간초과....ㅠ 어디가 문제인지 잘 모르겠다.

두번째 시도

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

public class 골드바흐의추측 {  

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

        boolean[] bool = new boolean[1000001];  
        Arrays.fill(bool, true); //bool의 기본값을 true로 변경.  

        for(int i=3; i<1000001; i++){  
            if(bool[i]){  
                for(int j=i+i; j<1000001; j=j+i){  
                    bool[j] = false; // 6 -false  9 , 12
                }  
            }  
        }  // ~체로 걸러논다. 걸러진값은 false

        while (true){  
            int n = Integer.parseInt(br.readLine());  
            if(n == 0) break;  

            int count = 0;  

            for(int i=3; i<1000001; i++){  
                if(bool[i] && bool[n-i]){  
                    System.out.println(n + " = " + i + " + " + (n-i));  
                    count = 1;  
                    break;  
                }  
            }  
            if(count == 0){  
                System.out.println("Goldbach's conjecture is wrong.");  
            }  
        }  
    }  
}

이렇게 작성하여 어떻게든 풀었다. 좀더 공부가 필요하다.

1. 에라토스테네스의 체 알고리즘을 통해 1000000까지 각 소수 여부를 구한 뒤 입력받은 n이 0이 아닐 경우에 while문을 계속해서 수행한다.

2. while문 내부에서는 다시 for문을 통해 해당 값이 참(소수)이고 n-i 번째 값 또한 참(소수)이라면 문제에서

   요구하는 출력 형식에 맞게 값들을 출력한다.

3. 또한, count 값을 1로 갱신한 뒤 count 값을 확인하여 그 값이 0이라면 두 홀수 소수의 합으로 n을 나타낼 수 없기 때문에 문제에서 주어진 문자열을 출력한다.