백준6588_골드바흐의 추측

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

 

 

package backjoon;
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
// ***********입출력 잘 살피자****************
 
public class b6588_골드바흐의추측_최성호 {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int[] arr = new int[500000];
 
        // arr에 홀수이면서 소수인 값들 저장
        int arr_index = 0;
        boolean flag = false;
        for (int i = 3; i < 1000000; i += 2) {
            flag = true;
            for (int j = 3; j * j <= i; j++) { // 루트값을 활용
                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                arr[arr_index++] = i;
            }
        }
 
        while (true) {
 
            int number = Integer.parseInt(br.readLine());
            if (number == 0)
                break;
 
            // 골드바흐의 추측 검증
            boolean flag2 = false;
            boolean flag3 = true;
            for (int j = 0; arr[j] < number; j++) { // 더해지는 홀수이면서 소수인 값은 numbr보다는 작아야됨 , 처음에는 arr끝까지 탐색해서 시간초과 계속 발생
                for (int k = j; arr[k] < number; k++) { // 마찬가지
                    if (number == arr[j] + arr[k]) {
                        bw.write(number + " = " + arr[j] + " + " + arr[k] + "\n"); // 홀수이면서 소수인 값의 합이 여러개 나올때 b-a가 가장 큰값을 출력이기때문에 굳이 다른 조건 필요x
                        bw.flush();
                        flag2 = true;
                        flag3 = true;
                        break;
                    } else {
                        flag3 = false; // 아닌값이 들어올때 flase로
                        continue;
                    }
                }
                if (flag2 == true) // 안해주면 여러개 있을  다 출력함
                    break;
            }
            if (flag3 == false) // 가능한 모든 조합의 합을 살펴봤지만 없으면 출력
                bw.write("Goldbach's conjecture is wrong.");
        }
 
    } // end of main
}