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

내 풀이

이 문제의 정수 n의 크기는 최대 1000000이기 때문에 많은 양의 소수를 구하게 될 것을 예상되어, 에라토스테네스의 체 알고리즘을 이용했다.

처음엔 입력받은 정수 n의 소수를 잘 구해놓고, 소수 두 개를 더해 정수 n이 되는 가장 작은 소수와 가장 큰 소수를 출력하는 부분에서 잘못 생각하여 다음 코드의 출력 부분에서 많이 헤맸다.

for (int i = 3; i < isPrime.length; i+=2) {
    if (isPrime[i]) {
        for (int j = i + 2; j < isPrime.length; j+=2) {
            if (isPrime[j] && i + j == n) {
                sb.append('\n').append(n).append(" = ").append(i).append(" + ").append(j);
                break;
            }
        } 
		break;
    }
}
System.out.println(sb);

예를들어 정수 n인 20의 소수는 2, 3, 5, 7, 11, 13, 17, 19인데, 20 = 3 + 17 이므로 규칙이 i번째 소수와 n-i번째 소수를 더하면 정수 n이 되는 것이다.

이런 규칙을 이용하지 못하고 엉터리 코드를 짜서 출력하려고 했기 때문에 계속해서 오류가 났다.

규칙을 알게되고 새롭게 작성한 정답 코드는 다음과 같다.

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

public class Main {
    static final int MAX = 1000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));

        boolean[] isPrime = new boolean[MAX+1];

        for (int i = 3; i < isPrime.length; i+=2) {
            isPrime[i] = true;
        }

        for (int i = 3; i <= Math.sqrt(MAX); i+=2) {
            for (int j = i*i; j <= MAX; j += i) {
                isPrime[j] = false;
            }
        }

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

            if (n == 0)
                break;

            boolean possible = false;
            for (int i = 3; i <= n/2; i+=2) {
                if (isPrime[i] &&  isPrime[n-i] && i + (n-i) == n) {
                    System.out.println(n+" = "+i+" + "+(n-i));
                    possible = true;
                    break;
                }
            }

            if (!possible)
                System.out.println("Goldbach's conjecture is wrong.");
        }
    }
}