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

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

9020번: 골드바흐의 추측

 

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것입니다.

그러한 두 소수를 골드바흐 파티션이라고 합니다.

아래는 골드바흐 파티션의 예제입니다.

• 8 = 3 + 5
• 10 = 5 + 5
• 16 = 5 + 11

골드바흐의 추측은 주어진 짝수가 n이라고 했을 때, n은 n보다 작은 두 소수 a, b의 합으로 나타낼 수 있습니다.

• n = a + b

이때 a > b 라면 n - a = b로 나타낼 수 있습니다. 

따라서 주어진 짝수 n보다 작은 소수 중에 위의 식을 만족하는 a, b를 구하여 답을 구할 수 있습니다.

추가적으로 골드바흐 파티션이 여러개 일 경우 두 소수의 차이가 가장 작은 것을 출력합니다.

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(br.readLine()); //테스트 케이스의 개수
		String answer = ""; // 골드바흐 파티션

		for (int a = 0; a < T; a++) { // 테스트 케이스의 개수만큼 반복

			int num = Integer.parseInt(br.readLine()); // 주어진 짝수 num

			for (int i = num; i >= num / 2; i--) { 
            //  num보다 작은 소수를 찾는다. 
            //  단, 두 소수의 차가 최소 지점인 0까지만 검사하면 되기 때문에 num/2 까지 검사한다.
				if (check(i)) { // 소수 찾기
					if (check(num - i)) { // 다른 한쪽의 소수 검사 (b = n - a)
						answer = (num - i) + " " + i; // 둘다 소수일 경우 정답으로 출력
					}			
				} else {
					continue;
				}
			}
			bw.write(answer + "\n");
		}

		br.close();
		bw.flush();
		bw.close();
	}

	public static boolean check(int num) {
		if (num == 1) {
			return false;
		}

		if (num == 2) {
			return true;
		}

		for (int i = 2; i <= (int) Math.sqrt(num); i++) {
			if (num % i == 0) {
				return false;
			}
		}

		return true;
	}
}