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

문제 링크 : https://www.acmicpc.net/problem/6588

 

에라토스테네스의 체를 이용한다.

2부터 시작해 자기자신을 빼고 배수에 해당하는 수를 모두 지운다.

boolean[] prime = new boolean[primeLength + 1];
Arrays.fill(prime, true);
// 제곱근까지만 봐도 충분함
for (int i = 2; i <= Math.sqrt(primeLength); i++) {
    if (!prime[i]) continue;
    for (int j = i * 2; j <= primeLength; j += i) {
        prime[j] = false;
    }
}

 

 

두 수를 더하는 것이니 절반까지만 돌아도 충분하다. 나머지 한 수가 채워주기 때문.

        String input;
        while (!(input = br.readLine()).equals("0")) {
            int N = Integer.parseInt(input);
            boolean flag = false;
            // 소수가 3부터 시작하므로 3부터, 절반까지만 돌아도 되고, 홀수소수만보니 2씩만 증가한다
            for (int i = 3; i <= primeLength / 2; i += 2) {
                int B = N - i;
                if (prime[i] && prime[B]) {
                    bw.write(N + " = " + i + " + " + B + "\n");
                    flag = true;
                    break;
                }
            }
            if (!flag)
                System.out.println("Goldbach's conjecture is wrong.");
        }
        bw.flush();