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

 

문제

6588번: 골드바흐의 추측

 

알고리즘

에라토스테네스의 체

 

풀이

테스트케이스가 최대 10만개이기 때문에

에라토스테네스의 체를 이용해 미리 100만까지의 소수를 전부 구하고,

 

입력으로 들어온 각 수에 대해 i를 1부터 50만까지 증가시키며

i 도 소수이고 n-i 도 소수라면 정답 문자열에 추가한다.

 

* i 를 작은 값부터 증가시키므로 i와 n-i 가 소수일 때가 b-a가 가장 큰 경우이므로 더 탐색하지 않아도 된다.

 

 

코드

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

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

		int MAX = 1_000_000;
		boolean[] prime = new boolean[MAX + 1];
		Arrays.fill(prime, true);
		prime[1] = false;

		for (int i = 2; i * i <= MAX; i++) {
			if (!prime[i]) continue;

			for (int j = i * 2; j <= MAX; j += i)
				prime[j] = false;
		}

		while (true) {
			int n = Integer.parseInt(br.readLine());
			if (n == 0) break;

			for (int i = 1; i <= MAX / 2; i++) {
				if (prime[i] && prime[n - i]) {
					sb.append(n).append(" = ").append(i).append(" + ").append(n - i).append("\n");
					break;
				}
			}
		}

		System.out.println(sb);
	}
}