[백준] 300 - 수학 1 : 골드바흐의 추측 (6588번 JAVA)

[백준] 300 - 수학 1 : 골드바흐의 추측 (6588번 JAVA)

---

[풀이 과정]

1. n의 최대값인 1,000,000 까지의 소수 여부를 구해 놓는다.

2. i = 3 부터, 홀수만 비교, (i , n-i) 순서쌍의 소수 여부를 체크한다.

3. 순서쌍이 모두 소수인 경우, i를 작은 값, n-i를 큰 값으로 하여, 출력한다.

---

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

public class Main{

    public static boolean[] prime;
    
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        /*
         매 테스트 마다 prime 배열을 새로 생성하는 경우 
         최악의 경우 : 100,000 * 1,000,000 의 반복을 해야 한다.
         따라서 미리 n의 최대값인 1,000,000 까지 prime 배열을 생성 해놓는다. 
        */
        
        prime = new boolean[1000000 + 1];
        make_prime(1000000);

        while(true){

            int n = Integer.parseInt(br.readLine());

            if (n == 0){
                break;
            }

            int s = 0;
            int b = 0;
            for(int i=3; i<=n; i+=2){

                if (prime[i] == false && prime[n-i] == false){
                    s = i;
                    b = n-i;
                    break;
                }
            }

            if(s % 2 == 0 || b % 2 == 0){
                bw.write( "Goldbach's conjecture is wrong."+"\n");
            }
            else {
                bw.write(n + " = " + s + " + " + b + "\n");
            }
        }
        bw.flush();
        bw.close();
    }

    public static void make_prime(int n){
        prime[0] = prime[1] = true; 

        for(int i = 2; i<=Math.sqrt(n); i++){
            if (prime[i] == true){
                continue;
            }
            for (int j = i * i; j<n+1; j+=i){
                prime[j] = true;
            }
        }

    }
}