[BOJ6588] 골드바흐의 추측

문제 설명

문제 링크

코드 리뷰

에라토스테네스의 체를 할 줄 아느냐 모르냐보다 테스트케이스를 입력받기전에 딱 한번 에라토스테네스의 체로 모든 소수를 뽑아놓고 시작하느냐 안하느냐가 중요한 문제인듯.

근데 에라토스테네스의 체를 배우면, 사전에 전처리를 하는 부분도 많이들 연습 하시니깐 어려운 문제는 아니었을 것 같다.

또한 전처리와 에라토스테네스의 체를 할 줄 알면, 그 이후는 답을 구했는데도 계속 보는 경우만 아니면 어떻게 풀어도 대부분 시간초과 걱정은 없을 것 같다.

문제가 답이 여러개일 경우에는 두 항의 차가 제일 작은게 아니라 큰 것을 구하라 했으니깐 앞에서부터 탐색하다가 답이 구해지면 더 이상 볼 필요 없이 바로 탈출하면 된다.

import java.io.*;
import java.util.*;

public class BOJ6588_골드바흐의추측 {
	static boolean[] bd = new boolean[1000001];
	static int N;
	public static void main(String[] args) throws Exception {
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		pp();
		while(true) {
			N = Integer.parseInt(br.readLine());
			boolean flg = false;
			if(N==0) break;
			for(int i=3; i<N; i++) {
				if(bd[i]) continue;
				if(!bd[N-i]) {
					flg = true;
					sb.append(N+" = ").append(i).append(" + ").append(N-i).append("\n");
					break;
				}
			}
			if(flg == false) sb.append("Goldbach's conjecture is wrong\n");
		}
		System.out.println(sb);
		
	}
	static void pp() {
		for(int i=2; i<=1000000; i++) {
			if(bd[i]==true) continue;
			for(int j=2; j*i<=1000000; j++) {
				bd[i*j]=true;
			}
		}
	}
}