[P&B] #101 BAEKJOON 17103

백준 17103번 골드바흐 파티션 JAVA

문제 설명

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

 

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

 

출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

 

나의 문제 풀이 코드

import java.io.*;

public class bj17103 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        // 에라토스테네스의 체를 사용하여 소수를 미리 구해놓습니다.
        boolean[] isPrime = new boolean[1000001];
        findPrimes(isPrime);

        while (T > 0) {
            long num = Long.parseLong(br.readLine());
            long result = countGoldbachPartitions(num, isPrime);
            sb.append(result).append("\n");
            T--;
        }

        bw.write(sb.toString());
        bw.close();
    }

    // 에라토스테네스의 체를 사용하여 소수를 찾습니다.
    private static void findPrimes(boolean[] isPrime) {
        for (int i = 2; i * i <= 1000000; i++) {
            if (!isPrime[i]) {
                for (int j = i * i; j <= 1000000; j += i) {
                    isPrime[j] = true;
                }
            }
        }
    }

    private static long countGoldbachPartitions(long N, boolean[] isPrime) {
        long count = 0;

        for (int i = 2; i <= N / 2; i++) {
            if (!isPrime[i] && !isPrime[(int) (N - i)]) {
                count++;
            }
        }
        return count;
    }
}

 

문제 풀이 코멘트

이 문제에서도 에라토스테네스의 체를 사용하여 소수를 찾는 방법을 사용했습니다. 하지만 이전처럼 수를 입력받을 때마다 에라토스테네스의 체로 소수를 구하여 골든바흐 파티션을 구하기엔 시간 복잡도가 높아집니다.

그래서 시작부터 에라토스테네스의 체를 사용하여 N의 입력 가능 범위까지 소수를 찾아둡니다. 그리고 입력받은 수와 소수 배열을 매개변수로 넘겨 골든바흐 파티션을 구합니다.

Goldbach 파티션은 주어진 짝수 N을 두 소수의 합으로 나타내는 것입니다. 따라서 i를 2부터 N/2까지 순회하면서, i와 (N - i)가 모두 소수인 경우를 찾아야 합니다. 왜냐하면 두 소수의 합으로 N을 나타낼 수 있기 때문입니다. 여기서 왜 i와 (N - i)가 모두 소수인 경우,  두 소수의 합이 N인지 이해가 안될 수 있습니다.

두 소수의 합이 N이 되는 이유는 짝수 N을 소수의 합으로 나타낼 때, 그 원리에 있습니다.
짝수 N을 소수의 합으로 나타내는 경우, 짝수 N은 다음과 같이 나타낼 수 있습니다.
N = p + q
여기서 p와 q는 소수이므로, 둘 다 1과 자기 자신 외에는 다른 어떤 수로도 나누어지지 않습니다. 따라서 p와 q를 더해서 N을 만들면, 다른 어떤 수로도 나누어지지 않는 N이 됩니다.
이것이 왜 i와 (N - i)가 모두 소수인 경우, 두 소수의 합이 N이 되는지의 원리입니다. i와 (N - i)가 모두 소수인 경우, 두 소수를 더하면 N이 되며, 이는 N을 소수의 합으로 나타낸 것입니다.

그리고 코드에서 i는 배열의 인덱스이자 소수를 의미하기 때문에 !isPrime[i] && !isPrime[(int) (N - i)]가 성립 시 Goldbach 파티션이라고 할 수 있어 count가 증가하게 되는 것입니다.