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

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

문제 출처 : https://www.acmicpc.net/problem/6588

답을 찾는 건 어렵지 않으나 시간 초과의 늪에 빠지는 문제

에라토스테네스의 체 공식을 통해 소수를 판별하기 위한 시간을 최대한 줄여나가야 함

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Problem6588 {
 
    public static boolean[] s = new boolean[1000000];
    
    public static void solution() { // 소수 정렬 함수
        
        // 소수는 true, 아니면 false
        for (int i = 2; i < s.length; i++) { 
            s[i] = true; // 일단 모두 true로
        }
        
        s[0] = s[1] = false; // 0과 1은 소수 아니므로 false
        
        for (int i = 2; i < (int)Math.sqrt(s.length) ; i++) {
            for (int j = i*2; j < s.length; j+=i) { // 2와 3은 소수이기 때문에 제외하고 부터 반복문
                s[j] = false; // 소수 아닌건 false로 처리
            }
        }
        
    }
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        solution();
        
        while(true){ 
            int num = Integer.parseInt(br.readLine());
            if(num == 0 || num <= 4) break; // 0이거나 4이하면 종료
            
            boolean check = false;
            
            for (int i = 2; i <= num/2; i++) { // 절반만 봐도 찾기 가능
                if(s[i]){ // i와 num-i가 모두 소수 일 때 출력 후 종료
                    if(s[num-i]){
                        System.out.println(num + " = " + i + " + " + (num-i));
                        check = true;
                        break;
                    }
                }
            }
            
            if(!check) System.out.println("Goldbach's conjecture is wrong.");
        }
    }
 
}