골드바흐의 추측

1. 문제 설명

"4보다 큰 모든 짝수 자연수는 홀수인 두 소수의 합으로 표현될 수 있다."
ex) 8 = 3 + 5, 20 = 3 + 17, 42 = 5 + 37
위와 같은 골드바흐의 추측이 맞는지 확인하는 프로그램 작성

입력 형식

첫 줄에는 테스트케이스의 수 T가 주어진다. T는 100이하의 자연수이다.

테스트케이스의 각 줄에는 골드바흐의 추측이 성립하는지 확인해보고자 하는 6이상 백만이하의 자연수가 하나 주어진다.

출력 형식

각 테스트케이스마다 정답을 두 줄로 출력한다.

테스트케이스의 첫 줄에는 테스트케이스의 번호를 Case #%d: 형식으로 출력한다.
두 번째 줄에는 검증 결과를 출력한다.
주어진 숫자에 대해 골드바흐의 추측이 성립했다면 해당 숫자와 두 홀수 소수를 x = a + b 형식으로 출력한다.
성립하는 조합이 여러가지하면 a가 가장 작은 정답을 출력한다.
성립하는 조합이 존재하지 않는다면 -1을 출력한다.

2. 알고리즘 접근

두 카드 알고리즘 << 이 알고리즘을 통해 target = p + q 방식을 응용하여 접근한다
위 알고리즘을 이용해 두 홀수의 조합을 고려하고
소수 판별 알고리즘을 이용하여 코드를 구현한다

3. 소스코드

public class Main {
	public static final Scanner scanner = new Scanner(System.in);
	public static final int MAX_VALUE = 1000000;
	public static final Sieve sieve = new Sieve(MAX_VALUE);

	public static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void testCase(int caseIndex) {
		int x = scanner.nextInt();

		int a = -1;
		int b = -1;
		
		// p+=2 : 홀수만 사용, x / 2 = 작은 정답으로 출력하기 위해
		for(int p = 3; p <= x / 2; p += 2){
			int q = x - p;
			if(sieve.isPrime[p] == true && sieve.isPrime[q] == true){
				a = p;
				b = q;
				break;
			}
		}

		// 정답을 출력한다
		System.out.printf("Case #%d:\n", caseIndex);
		if(a > 0 && b > 0)
		{
			System.out.printf("%d = %d + %d\n", x, a, b);
		}else{
			System.out.println(-1);
		}
	}

	public static void main(String[] args) throws Exception {
		int caseSize = scanner.nextInt();

		for (int caseIndex = 1; caseIndex <= caseSize; caseIndex += 1) {
			testCase(caseIndex);
		}
	}
}
class Sieve{
	boolean[] isPrime;
	public int maxValue;
	
	Sieve(int maxValue){
		this.maxValue = maxValue;
		isPrime = new boolean[maxValue +1];
		this.fillSieve();
	}
	
	public void fillSieve(){
		Arrays.fill(isPrime, true);
		
		for(int i = 2; i <= maxValue; i++){
			if(isPrime[i] == false) continue;
			
			for(long mul = (long)i * i; mul <= maxValue; mul+=i){
				isPrime[(int)mul] = false;
			}
			
		}
	}
}