[BAEKJOON] 9020번

<Java>

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        run();
    }
    
    public static void run() {
        int t;
        int[] n;
        Scanner scanner = new Scanner(System.in);
        int a = -1, b = -1;
        
        t = scanner.nextInt();
        n = new int[t];
        
        for(int i = 0; i < t; ++i) {
            n[i] = scanner.nextInt();
        }
        
        for(int i = 0; i < t; ++i) {
            for(int j = 2; j <= n[i]/2; ++j) {
                if(isPrime(j) && isPrime(n[i] - j)) {
                    a = j; b = n[i] - j;
                }
            }
            
            System.out.printf("%d %d\n", a, b);
        }
        
        scanner.close();
    }
    
    public static boolean isPrime(int n) {
        if (n != 2) {
            if ((n % 2 == 1) && (n != 1)) {
                for (int i = 3; i*i <= n; i += 2) {
                    if (n%i == 0) { return false; }
                }
            } else { 
                return false; 
            }
        }
 
        return true;
    }
 
}

입력값은 짝수로 주어진다고 했으므로 별다른 검증은 거치지 않는다.

 n 에 입력값의 목록이 형성되고, 요소를 하나씩 불러온 다음,  j + (n[i] - j) 로 쪼갠다.

따라서  j 의 범위를 무조건  1 ≤ j ≤ n[i]/2 로 설정하면, 최종적으로  a 와  b 는 가장 차이가 작은 골드바흐 파티션이 된다.

실행 시간: 1308ms

<Java: Eratosthenes`s sieve>

import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        run();
    }
    
    public static void run() {
        int t;
        boolean[] isComp = new boolean[10001];
        Scanner scanner = new Scanner(System.in);
        int a = -1, b = -1;
        int[] n;
        
        t = scanner.nextInt();
        n = new int[t];
        
        for(int i = 2; i < isComp.length; ++i) {
            if(!isComp[i]) {
                for(int j = i << 1; j < isComp.length; j += i) {
                    isComp[j] = true;
                }
            }
        }
        
        for(int i = 0; i < t; ++i) {
            n[i] = scanner.nextInt();
        }    
        
        for(int i = 0; i < t; ++i) {
            for(int j = 2; j <= n[i]/2; ++j) {
                if(!(isComp[j] || isComp[n[i] - j])) {
                    a = j; 
                    b = n[i] - j;
                }
            }
        
            System.out.printf("%d %d\n", a, b);
        }
        
        scanner.close();
    }
}
 

실행 시간: 800ms

킹갓토스빛네스...