백준 9020번 : 골드바흐의 추측 [JAVA]

문제 링크 : https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

문제 |

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

 

입력 |

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

 

출력 |

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

 

제한 |

• 4 ≤ n ≤ 10,000

import java.io.*;

public class Main {
	public static boolean[] primeNums = new boolean[10001];
	
	public static void getPrime() {
		for(int i = 2; i < Math.sqrt(primeNums.length); i++) {
			if(primeNums[i])
				continue;
			for(int j = i * i; j < primeNums.length; j += i)
				primeNums[j] = true;
		}
	}
	
	public static void main(String[] args) throws IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			int n = Integer.parseInt(br.readLine());
			
			getPrime();
			
			int count = 0;
			
			while(count != n) {
				count++;
				int getNum = Integer.parseInt(br.readLine());
				int a = getNum / 2;
				int b = getNum / 2;
				
				while(a > 0) {
					if(primeNums[a] == false && primeNums[b] == false) {
						System.out.println(a + " " + b);
						break;
					}
					else {
						a--;
						b++;
					}
				}
			}
	}
}

 이번 문제도 소수 구하기 문제의 연장선이다. 입력된 숫자를 두 소수의 합으로 나타내되, 두 소수의 차이가 가장 적은 것을 추출해내야 한다. 처음에 얼핏보면 경우의 수가 너무 많아 걸러내기 힘들 것 같지만 중간부터 하나씩 차이를 벌려나가면서 소수인 것을 찾아낸다고 하면 어렵지 않다.

 

	public static void main(String[] args) throws IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			int n = Integer.parseInt(br.readLine());
			
			getPrime();

 앞서 풀었던 4948번 베르트랑 공준 문제가 기억나는가? 그 문제와 마찬가지로 비슷한 시작을 한다. 소수임을 판별하기위해 그때그때 소수 검사를 하기보다는 미리 소수검사 배열을 만들어서 나온 숫자를 대입해 소수인지 아닌지 분간하는 것이 더 효율적이다. 그래서 몇 개의 숫자를 입력받을 지 변수 n을 통해서 입력받고, getPrime() 메소드를 통해 소수 판별 배열을 채워넣는다.

 

	public static boolean[] primeNums = new boolean[10001];
	
	public static void getPrime() {
		for(int i = 2; i < Math.sqrt(primeNums.length); i++) {
			if(primeNums[i])
				continue;
			for(int j = i * i; j < primeNums.length; j += i)
				primeNums[j] = true;
		}
	}

 Main 클래스 안에 들어있는 boolean형 배열 primeNums를 문제 제한 조건에 맞춰 10000에다가 1을 더한 10001의 크기로 만들어준다. 여기서 false이면 소수이고, true이면 소수가 아닌 것으로 판별한다. boolean 배열에는 기본적으로 false값이 들어가 있기 때문에 2부터 차례대로 2 자기 자신은 제외하고 제곱한 숫자들부터 true로 채워 소수가 아님을 표시한다.

 

			int count = 0;
			int getNum, a, b;
			
			while(count != n) {
				count++;
				getNum = Integer.parseInt(br.readLine());
				a = getNum / 2;
				b = getNum / 2;
				
				while(a > 0) {
					if(primeNums[a] == false && primeNums[b] == false) {
						System.out.println(a + " " + b);
						break;
					}
					else {
						a--;
						b++;
					}
				}
			}

 count 변수 값을 생성해 몇 번 입력을 받을 지 반복문 탈출 조건을 두었다. 첫번째 while문이 한번씩 돌때마다 count값이 증가하여 앞서 입력한 반복 횟수 n번을 충족하면 반복문에서 탈출한다. 그리고 미리 생성해놓은 getNum 변수로 입력값을 받고 a와 b에는 각각 getNum 변수에 담긴 입력값의 중간값을 넣는다.

 

 그리고 두번째 while문을 동작시켜 a와 b가 getPrime() 메소드로 미리 만들어놓은 소수 판별 배열과 비교하여 소수인지 구분한다. 만약 둘 다 소수라면 가장 차이가 적고, 그 둘을 합했을 때 getNum 변수값이므로 골드바흐 파티션이라고 할 수 있다. 그래서 if문을 통해 골드바흐 파티션 값인 a와 b를 출력하고 두번째 while문을 탈출한다. 만약 둘 중 하나라도 소수가 아니라면 else문을 통해 차이를 1씩 벌려나간다. 문제에서 골드바흐 파티션 출력 시 작은 값을 먼저 출력하라는 조건이 있으므로 먼저 출력되는 a값은 감소시키고 나중에 출력되는 b 값은 증가시켰다.