[백준 알고리즘 풀이] 9020번 골드바흐의 추측

문제를 해결하는 방법은 많지만, 간단하게 두 소수의 합으로 표현가능한 짝수를 모조리 구해버린 다음 메모리에서 꺼내면 깔끔하게 클리어된다.

import java.util.Scanner;

/*
 * 9020번 골드바흐의 추측
 */
public class Main {
 
  public static void main(String[] args) throws Exception {
    boolean[] primes = new boolean[10002];
    primes[0] = true;
    primes[1] = true;
    for (int i = 2; i < primes.length; i++) {
      if (!primes[i]) {
        for (int j = 2; j < primes.length; j++) {
          if (i * j >= primes.length)
            break;
 
          primes[i * j] = true;
        }
      }
    }
 
    String[] memo = new String[10001];
    for (int i = 0; i < 10001; i++) {
      if (!primes[i]) {
        for (int j = i; j < 10001 - i; j++) {
          if (!primes[j] && (i + j) % 2 == 0) {
            if (i + j < 10001) {
              memo[i + j] = i + " " + j;
            }
          }
        }
      }
    }
 
    Scanner sc = new Scanner(System.in);
    int t = Integer.parseInt(sc.nextLine());
    while (t > 0) {
      System.out.println(memo[Integer.parseInt(sc.nextLine())]);
      t--;
    }
    sc.close();
  }
 
}