백준

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

거북이같은곰 2021. 11. 16. 07:06


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

public class Main {
	static ArrayList<Integer> list;
	static boolean[] prime = new boolean[1000001];
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		isPrimeNumber();
		prime[2] = true;
		while(true) {
			int N = Integer.parseInt(br.readLine());
			if(N == 0) {
				break;
			}
			result(N);
		}
		System.out.println(sb);
	}
	static void isPrimeNumber() {
		list = new ArrayList<>();
		for(int i = 2; i <= 1000; i++) {
			if(prime[i])
				continue;
			for(int j = i+i; j <= 1000000; j += i) {
				prime[j] = true;
			}
		}
	}
	static void result(int N) {
		for(int i = 3; i <= 1000000; i++) {
			if(i >= N) {
				sb.append("Goldbach's conjecture is wrong.").append("\n");
				return;
			}
			if(prime[i] == false) {
					int a = N - i;
					if(prime[a] == false) {
						sb.append(N+" = "+i+" + "+a).append("\n");
						return;
					}
			}
		}
	}
}