백준 9020 골드바흐의 추측(Java)

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

9020번: 골드바흐의 추측

---

 

해석 및 팁

 

---

 

이 문제는 에라토스테네스의 채를 활용하면 되는 문제입니다. 먼저 n보다 작은 소수를 에라토스테네스의 채를 활용하여 구해준 후 주어진 n을 반으로 나누어서 둘 다 소수가 될 때까지 더하거나 빼주면 되는 문제입니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {

  static int n;
  static boolean[] arr = new boolean[10001];

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();
    
    arr[0] = true;
    arr[1] = true;

    int t = sc.nextInt();
   
    for(int i = 0; i < t; i++) {
      n = sc.nextInt();
      int div = n / 2;
      demical();

      while(true) {
        if(arr[div] == false && arr[n - div] == false) break;
        div++;
      }
      
      sb.append((n - div)+" "+div).append("\n");
    }
    
    System.out.println(sb);
  }

  static void demical() {
    for(int i = 2; i <= Math.sqrt(n); i++) {
      if(arr[i] == true) continue;
      for(int j = i * i; j <= n; j += i) arr[j] = true;
    }
  }
  
}