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

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

6588번: 골드바흐의 추측

 

출력값 a, b 는 홀수에 소수이므로 항상 3부터 시작

따라서 b - a가 가장 큰 값은 a가 3일 때임

에라토스테네스의 체로 미리 전체값 소수 판별

 

 

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


public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();


        int n = 1000000;
        boolean[] arr = new boolean[n + 1];
        Arrays.fill(arr, true);

        for(int i = 2; i <= Math.sqrt(n); i++) {
            if(arr[i]) {
            int j = 2;  
                while(i * j <= n) {
                    arr[i * j] = false;
                    j++;
                }
            }
        }


        boolean isEnd = false;
        while(!isEnd) {
            int num = Integer.parseInt(br.readLine());
            if(num == 0) {
                isEnd = true;
            	break;
        	}

        	boolean isProve = false;
        	for(int j = 3; j < num; j++) {
                if(arr[j]) {
                    if(arr[num-j]) {
                        sb.append(num).append(" = ").append(num - j).append(" + ").append(j).append("\n");
                        isProve = true;
                        break;
                    }
                } 
            }
            if(!isProve) {
            	sb.append("Goldbach's conjecture is wrong.").append("\n");
            }

        }

        System.out.println(sb);


    }
}