[백준-9020번/Java] 골드바흐의 추측

* 소수판정 : 제곱근 범위 나누기법 사용

* 두 소수의 차이가 가장 작은 골드바흐 파티션을 찾기 위해서 num/2 부터 1씩 줄여 나가면서 찾음.

import java.io.*;
import java.util.*;

public class Main {

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

		Scanner scan = new Scanner(System.in);

		int[] arr = new int[10000 + 1];

		for (int i = 1; i < arr.length; i++) {
			if (i == 1) {
				arr[i] = -1;
			} else {
				arr[i] = i;
			}
		}

		// 제곱근 범위 나누기법
		for (int i = 3; i < arr.length; i++) {
			for (int j = 2; j <= Math.sqrt(i); j++) {
				if (i != j && i % j == 0) {
					arr[i] = -1;
				}
			}
		}

		int T = scan.nextInt();
		int num1 = 0;
		int num2 = 0;

		for (int i = 0; i < T; i++) {
			int num = scan.nextInt();
			for (int j = num / 2; j > 0; j--) {
				if (arr[j] != -1 && arr[num - j] != -1) {
					num1 = arr[j];
					num2 = arr[num - j];
					break;
				}
			}
			System.out.println(num1 + " " + num2);
		}

		scan.close();
	}

}