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

백준알고리즘 #9020 골드바흐의 추측 문제

임의의 짝수 n에 대해 소수 2개의 합으로 n을 나타내는 골드바흐 파티션을 구하는 문제이다.

 

 

먼저 주어진 범위 10000만큼의 배열을 만들어 에라토스테네스의 체를 이용해 소수를 구해놓는다.

int[] a = new int[10001];
int check = 0;

for (int i = 2; i <= a.length - 1; i++) {
	for (int j = 2; j <= (a.length - 1) / 2; j++) {
		if (i * j > a.length - 1)
			break;
		a[i * j]++;
	}
}

이 소수들을 가지고 골드바흐 파티션을 구해보자.

 

 

위 a 배열에서 a[i*j]를 증가시켜 놓았으므로 소수라면 a[i]가 0이 될 것이다.

즉 a[i] == 0 이라는 조건을 넣으면 이 i 는 소수가 된다고 볼 수 있다.

이를 이용해 임의의 짝수 n 에 대해  i + j = n 을 만족하는 골드바흐 파티션을 구해보자.

for (int i = n / 2; i < n; i++) {
	for (int j = 1; j < n / 2 + 1; j++) {
		if (a[i] == 0 && a[j] == 0 && i + j == n) {
			System.out.println(j + " " + i);
			check = 1;
			break;
		}
	}
	if (check == 1)
		break;
}

반복하는 범위를 줄이고, 두 소수의 차이가 가장 작은 것을 구하기 위해

i (큰 수) 는 n / 2  부터 시작하고 j (작은 수)는 n / 2 + 1 까지만 반복한다.

만약 n을 2로 나눈 값부터 시작한다면 가장 먼저 나오는 i와 j가 골드바흐 파티션 중 가장 작은 차이를 가진 소수일 것이다. (50일 경우 25부터 시작하므로 31 29가 된다.)

 

if문을 이용하여 a[i] == 0 라는 조건과 a[j] == 0 그리고 i + j == n 이 3가지를 모두 만족시키기 위해 &&로 연결한다.

본문에 작은 수 부터 출력하라고 했으므로  j , i 를 순서대로 출력해주면 된다.

i (큰 수) 는 점차 증가하므로 조건을 만족하는 i 와 j 를 찾았다면 이 반복문을 빠져나와야 하는데 이를 위해 미리 만들어 둔 check 변수에 1을 대입시켜 break를 이용해 for문을 빠져나왔다. (다른 방법이 있을지도 모르겠다..)

 

전체 코드를 보면 다음과 같다.

import java.util.Scanner;

public class Back9020 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		int[] b = new int[t];
		for (int x = 0; x < t; x++) {

			int n = sc.nextInt();
			int[] a = new int[10001];
			int check = 0;

			for (int i = 2; i <= a.length - 1; i++) {
				for (int j = 2; j <= (a.length - 1) / 2; j++) {
					if (i * j > a.length - 1)
						break;
					a[i * j]++;
				}
			}

			for (int i = n / 2; i < n; i++) {
				for (int j = 1; j < n / 2 + 1; j++) {
					if (a[i] == 0 && a[j] == 0 && i + j == n) {
						System.out.println(j + " " + i);
						check = 1;
						break;
					}
				}
				if (check == 1)
					break;

			}
		}
	}

}