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

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

6588번: 골드바흐의 추측

소수찾기에서 사용한 아리스토테네스의 체 알고리즘을 이용하여 1000000까지 자연수의 소수 판별을 미리 한 후 prime이라는 boolean 배열에 담아둔다. 

a+b=N을 만족하고 prime[a]와 prime[b]가 둘 다 false인 a와 b를 찾기 위한 반복문을,  a=3, b=N-3부터 b가 a보다 작아질 때 까지 검사한다.

import java.util.*;

public class Main {
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int N;
		int cnt=0;
		
		boolean[] prime = new boolean[1000001];
		prime[1] = true;
		
		for(int i=2; i<1000001; i++) {
			if(prime[i])
				continue;
			
			for(int j=2; i*j<1000001; j++)
				prime[i*j]=true;
		}
		
		do {
			N=sc.nextInt();
			if(N==0) break;
			int a = 3;
			int b = N - a;
			
			while(true) {
				if(!prime[a]&&!prime[b]) {
					sb.append(N+" = "+a+" + " + b+"\n");
					break;
				}
				if(b<a) {
					sb.append("Goldbach's conjecture is wrong.\n");
					break;
				}
				b-=2;
				a+=2;
			}
			
		}while(true);
		
		System.out.println(sb);
	}
}