[백준 6588] 골드바흐의 추측

 

일단 소수배열을 구한다.

 

임의의 수 x 에 대하여 x, n-x 가 모두 소수일때 문제의 조건을 만족한다.

 

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        boolean prime[] = new boolean[1000001];
        for(int i=2; i<=1000000; i++)
            for(int j=i*2; j<=1000000; j+=i)
                prime[j] = true;
        
        while(true) {
            int n = Integer.parseInt(br.readLine());
            if(n == 0) break;
            
            boolean b = false;
            for(int i=3; i<=n; i++) {
                if(!prime[i] && !prime[n-i]) {
                    System.out.println(n + " = " + i + " + " + (n-i));
                    b = true;
                    break;
                }
            }
            if(!b) System.out.println("Goldbach's conjecture is wrong.");
        }
    }
}