[JAVA] 백준 9020번- 골든바흐의 추측

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

9020번: 골드바흐의 추측

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] arr = new int[100001];

        // 소수가 아니면 1으로
        for(int i=2; i<=Math.sqrt(arr.length); i++){
            for(int j=i*i; j<arr.length; j+=i){
                if(arr[j] == 0) arr[j] = 1;
            }
        }

        while(T-- >0){
            int n = Integer.parseInt(br.readLine());
            for(int i=n/2; i>0; i--){
                if(arr[i]!=1 && arr[n-i]!=1){ // 차가 적은 숫자들부터 차를 늘려나가며 검사
                    System.out.println(i+" "+(n-i));
                    break;
                }
            }
        }
    }
}

 

소수인 숫자들을 구하는건 에라토스테네스의 체를 사용했다.

차이가 제일 작은 두 소수를 구할 때 이중 for문을 돌려 했더니 시간 초과 났다. 

다른 풀이를 보니 중간에 있는 숫자들로 시작해 그 차이를 넓혀나가며 for문을 돌면 효율적으로 바로 찾을 수 있었다.