백준 - 6588번 - 골드바흐의 추측

6588번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static boolean[] prime;

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

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		makePrime(1000000);
		while (true) {

			int num = Integer.parseInt(bf.readLine());
			if (num == 0) {
				break;
			}
			for (int i = num-1; i>=0; i--) {
				if (prime[i] == false) {
					int j = num - i;
					if (prime[j] == false) {
						System.out.println(num+" = "+j+" + "+i);
						break;
					}
				}
				if (i == 0) {
					System.out.println("Goldbach's conjecture is wrong.");
				}
			}
		}
	}

	static boolean[] makePrime(int N) {
		prime = new boolean[N+1];
		prime[0] = true;
		prime[1] = true;

		for (int i = 2; i<=Math.sqrt(N); i++) {
			if (prime[i] == true) {
				continue;
			}

			for (int j = i * i; j<N+1; j=j+i) {
				prime[j] = true;
			}
		}
		return prime;
	}
}

풀이

---

어떤 짝수를 입력받았을때 그 수보다 작은 소수들의 합으로 되는경우를 출력하는 문제다.

에라토스테네스의 체로 소수를 구하고 대입을 해주는식으로 문제를 풀었다.

하지만 기존에 수를 받을때마다 에라토스테네스의 체로 그에 맞는 소수를 구하게 해놨던것이 시간초과로 이어졌다.

그래서 입력받는 최대 범위인 1000000내부의 소수를 에라토스테네스의 체로 구해놓고 반복문을 돌리니 성공했다.