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

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

6588번: 골드바흐의 추측

 

에라토스테네스의 체 알고리즘으로 소수를 판별해놓고,

 

반복문으로 i를 2~100만까지 증가시키면서

i가 소수이고, n-i가 소수인 경우에 출력한다.

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

public class P6588 {

	static boolean[] prime = new boolean[1000001];

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

		for (int i = 2; i < 1000001; i++) {
			prime[i] = true;
		}

		for (int i = 2; i < 1000001; i++) {
			if (prime[i] == true) {
				for (int j = i * 2; j < 1000001; j += i) {
					prime[j] = false;
				}
			}
		}

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n;
		while ((n = Integer.parseInt(br.readLine())) != 0) {

			for (int i = 0; i < n; i++) {
				if (prime[i] == true && prime[n - i] == true) {
					System.out.println(n + " = " + i + " + " + (n - i));
					break;
				}
			}

		}
	}

}