[백준 알고리즘] 9020 - 골드바흐의 추측

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

 

이 문제는 먼저 10,000 이하의 소수를 구한 뒤, 주어진 숫자를 소수의 합으로 구할 수 있는 경우 그 소수들을 출력하는 방식으로 해결할 수 있는 문제입니다.

 

만약 가능한 n의 골드바흐 파티션(주어진 수를 이루는 소수의 조합)이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다고 했기 때문에 소수를 구할 때 주어진 수 n을 반으로 나눈 뒤, 한쪽을 줄여가면서 맞는 소수가 있는지 확인했습니다.

 

자바 코드는 다음과 같습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        // 소수인 경우 true, 아니면 false
        boolean[] primeNum = new boolean[10001];
        Arrays.fill(primeNum, true);
        primeNum[0] = primeNum[1] = false;

        for (int i = 2; i * i < primeNum.length; i++) {
            for (int j = i * i; j < primeNum.length; j+=i) {
                primeNum[j] = false;
            }
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        // 테스트 케이스만큼 반복
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());

            // n / 2 부터 수를 줄여가면서 (a + b = n 일 때, a와 b의 차이가 적어야 하므로)
            for (int k = n / 2; k >= 2; k--) {
                // 입력된 수를 이루는 두 수가 소수인지 확인
                if (primeNum[k] && primeNum[n - k]) {
                    sb.append(k).append(" ").append(n - k).append("\n");
                    break;
                }
            }
        }

        System.out.print(sb);
    }
}