[JAVA] 백준 6588 - 골드바흐의 추측

문제 풀이 전 이론 - 1

- 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다

- 위의 문장에 3을 더하면

- 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다로 바뀐다.

- 이는 아직 증명되지 않은 문제이기 때문에 "추측"이다.

- 하지만 $10^18$이하에서는 참인 것이 증명되었기 때문에, 알고리즘 문제를 푸는데에는 전혀 문제가 없다.

 

문제 풀이

- 이 문제는 n의 최악의 경우가 100만이고, 테스트 케이스 문제이기 때문에

- 크기가 100만인 배열을 할당하여 미리 정답을 저장해놓고, 반복문을 통하여 입출력을 해야한다.

- 입력은 짝수를 받으며, 짝수 = 홀수(소수) + 홀수(소수)이므로, 소수들을 미리 배열에 저장해놓는 방법을 사용한다.

- 일단, 에라토스테네스의 체를 이용하여 100만 이하의 모든 소수들을 미리 배열에 할당해 놓을 것이다. 하지만, 100만 이하의 소수들의 개수를 정확하게 모르기 때문에 가변적으로 저장할 수 있도록 ArrayList를 사용한다.

- 반복문을 돌려서 ArrayList에 저장된 소수값을 가져와 a값에 할당한다. ex) 42 = 3 + b

- 그런데 b가 소수가 아니라면 i를 1 증가시켜 반복문을 돌린다. ex) 42 = 5 + b

- b가 소수가 나왔다면 반복문을 멈춘다. ex 42 = 5 + 37

 

public class Main {
	static final int MAX = 1000000;
	
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		ArrayList<Integer> prime = new ArrayList<Integer>(); // 1~100만까지 소수의 개수를 모르니까 가변적으로 / 테스트케이스에 100만이어서 미리 저장해놓음.
		boolean[] check = new boolean[MAX+1];
		
		EratosTenes(prime,check);
		
		while(true) {
			int n = scan.nextInt();
			if(n == 0) break;
			for(int i = 1; i <= prime.size(); i++) { // 홀수 + 홀수 = 짝수이어야되니까 i가 1 즉, 3부터 시작
				int p = prime.get(i); // 얘는 3부터 시작해서 5 7 11~임 (소수는 2만 짝수임을 참고)
				if(check[n - p] == false) {
					System.out.println(n + " = " + p + " + " + (n-p));
					break;
				}
			}
		}
	}
	
	public static void EratosTenes(ArrayList<Integer> prime, boolean[] check) {
		check[0] = check[1] = true;
		
		for(int i = 2; i*i <= MAX; i++) {
			if(check[i] == true) {
				continue;
			}
			
			prime.add(i);
			
		    for(int j = i+i; j<=MAX; j+=i) { // 2 , 3 본인들은 냅두고 J+=i로 배수만큼 반복 4,6 등은 이미 지워짐 i+i하면 소수인 본인들은 안지워짐.
		    	check[j] = true;
		    }
		}
	}
}

출력

문제로부터 얻어간 것

입력 값의 최악의 경우가 매우 큰 숫자이고 테스트 케이스 문제라면, 일단 배열에 저장해놓고 반복하여 입출력하는 방법을 생각해야한다.

이런 경우에는 일단 배열에 모든 소수들을 저장해놓아야 하므로 에라토스테네스의 체가 유용하게 사용된다. 에라토스테네스의 체를 구현했다면 골드바흐의 추측을 증명하는 것 자체는 어렵지 않다.