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

 

"에라토스테네스의 체"를안다면 쉽게 풀리는 문제이다.

 

에라토스테네스의 체란 간단히 말해

소수의 배수 = 소수가 아님을 이용한 것이다.

반복문을 돌며 가작 작은 소수인 2부터 배수를 지워주고 그다음 3 , 5 순으로 돌면서 배수를 지워준다.

이때 배열로 배수를 지우며, 이미 체크가 된 숫자는 소수가 아니므로 검사를 넘어간다.

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

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


        }
    }
}