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

오랜만에 알고리즘 하니까 머리가 안굴러가네욤....

소수판별을 맨 처음부터 세팅해놓고 진행하기

 ㄴ 비슷한 문제로 에라토스테네스의 체 ? 가 있음

시간초과 자꾸나서 소수판별 로직을 바꾸었음 자세한 내용은 주석 참고

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

public class bj6588 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		boolean[] isPrime = new boolean[1000001];
		isPrime[0] = true; // 소수를 false로 함
		isPrime[1] = true;
		// 처음엔 다 prime(false)으로 세팅
		// 배수는 prime이 아니므로 true
		for (int i = 2; i <= (int) Math.sqrt(1000000); i++) { 
			for (int j = 2; i * j < 1000001; j++) {
				isPrime[i * j] = true; // 소수가 아님
			}
		}

		while (true) {
			int n = Integer.parseInt(in.readLine());
			if (n == 0) {
				break;
			}
			boolean ans = false;
			for (int i = 2; i <= n / 2; i++) {
				if (!isPrime[i] && !isPrime[n - i]) {
					System.out.println(n + " = " + i + " + " + (n - i));
					ans = true;
					break;
				}
			}
			if (ans == false) {
				System.out.println("Goldbach's conjecture is wrong.");
			}
		}
	}
}