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

 

 

n이 10000이하이므로 10000까지의 소수를 저장해 놓는다.

두 소수의 차이가 가장 작아야 하므로 n/2를 기준으로 반복문을 돌며 소수 쌍을 찾아냈다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        int prime[] = new int[10001];
        for(int i=2; i<=10000; i++)
            for(int j=2; i*j<=10000; j++)
                prime[i*j] = 1;
        
        while(t-->0) {
            int n = sc.nextInt();
            
            for(int i=n/2; i>0; i--) {
                if(prime[i] == 0 && prime[n-i] == 0) {
                    System.out.println(i + " " + (n-i));
                    break;
                }
            }
        }
    }
}