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

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

https://www.acmicpc.net/problem/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 + "

"); } 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; } }

from http://hyunipad.tistory.com/77 by ccl(A) rewrite - 2021-10-14 00:01:16