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

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

 

2의 곱셈부터 해서

소수가 아닌 수를 체크해두어 판단한다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		boolean[] arr = new boolean[1000001];
		for (int j = 2; j < 1000001; j++) {
			if (arr[j])
				continue;
			for (int i = j * 2; i < 1000001; i += j) {
				arr[i] = true;
			}
		}
		while (true) {
			int num = Integer.parseInt(br.readLine());
			if (num == 0)
				break;

			int x = 0;
			int y = 0;
			for (int i = 3; i < num - 1; i += 2) {
				if (i % 2 != 0 && (num - i) % 2 != 0) {
					if (!arr[i] && !arr[num - i]) {
						x = i;
						y = num - i;
						break;
					}
				}
			}
			if (x == 0 && y == 0) {
				sb.append("Goldbach's conjecture is wrong.").append("\n");
			} else {
				sb.append(num).append(" = ").append(x).append(" + ").append(y).append("\n");

			}
		}
		System.out.println(sb);
	}

}