백준 6588번: 골드바흐의 추측 (JAVA)

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

먼저 에라토스테네스의 체로 1000000까지의 소수를 구한다.
그 후 소수들의 합을 구한다.
n의 범위에서 가장 큰 소수부터 하나씩 빼가면서 구한다. 가장 작은 소수는 3이니 n-3부터 시작한다. ( for(int i=n-3;i>=3;i--) )

원래는 ArrayList 를 썼는데 자꾸 시간초과가 나서 단순 반복문으로 바꾸었다.
StringBuilder 형식으로 시간을 더 줄여주었다.

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

public class Main{
	
	static final int MAX =1000001;
	static boolean[] isPrime = new boolean[MAX];
	static StringBuilder str;
	
	public static void Eratos() {
		isPrime[0] = isPrime[1] = false;
		
		for(int i=2; i*i<MAX; i++) {
			if(isPrime[i] == false) {
			for(int j=i*i; j<MAX; j+=i) {				
					isPrime[j] =true;
				}
			}
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n=0;
		
		Eratos();
		
		while(true) {
			n=Integer.parseInt(br.readLine());
			
			if(n==0) {
				break;
			}
			boolean check = false;
			
			StringBuilder str = new StringBuilder();
			
			for(int i=n-3;i>=3;i--) {
				if(!isPrime[i] && !isPrime[n-i]) {
					str.append(n+ " = "+(n-i)+ " + "+ i  +"\n");
					check=true;
					break;
				}
			}
			
			if(!check) {
				str.append("Goldbach's conjecture is wrong.");
			}
			
			bw.write(str.toString());
			bw.flush();
		}
		
		bw.close();
		br.close();
	}
}

비슷한 문제
https://www.acmicpc.net/problem/17103