8회차 - 골드바흐의 추측

1742년에 독일의 수학자 골드바흐는 자신의 추측한 바를 정리하여 오일러에게 편지로 전했다. 골드 바흐의 추측은 아래와 같다.

 

"4보다 큰 모든 짝수 자연수는 홀수인 두 소수의 합으로 표현될 수 있다."

 

 아래와 같은 예시들에서 골드바흐의 추측이 성립한다.

• 8 = 3 + 5
• 20 = 3 + 17
• 42 = 5 + 37

 

당신은 실제로 골드바흐의 추측이 성립하는지 프로그램을 작성해 확인해보고자 한다. 여러 숫자가 주어질 때 그 숫자들에 골드바흐의 추측이 성립하는지 확인하는 프로그램을 작성하시오.

 

입력 형식

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

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

 

출력 형식

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

• 테스트케이스의 첫 줄에는 테스트케이스의 번호를 Case #%d: 형식으로 출력한다.
• 두 번째 줄에는 검증 결과를 출력한다.

 

문제 출처

• University of Ulm Local Contest 1998

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


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;

		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;
	int maxValue;
	
	Sieve(int maxValue){
		this.maxValue = maxValue;
		isPrime = new boolean[maxValue+1];
		this.fillSieve();
	}
	private void fillSieve(){
		// 전체를 true 로 초기화
		Arrays.fill(isPrime, true);
		
		// 1은 false
		isPrime[1] = false;
		
		// 2부터 maxValue 까지 차례로 선정해서 소수가 아니면 스킵
		for( int num = 2; num <= maxValue; num += 1){
			// 소수가 아니면 SKIP
			if( isPrime[num] == false ){
				continue;
			}
			
			// 소수가 배수를 삭제해준다. (이때 멱수부터 삭제한다.)
			for( long mul = (long)num*num; mul <= maxValue; mul += num){
				isPrime[(int)mul] = false;
			}
		} 
	}
}