백준_9020 (골드바흐의 추측)

구현방법

1. 에라토스테네스의 체를 이용하여 2부터 입력받은 수 중 가장 큰 숫자까지의 소수 유무를 isPrime 배열에 저장한다.
2. 입력받은 숫자(n) 에서 i(소수)를 뺀 값(j) 가 소수이면 두개의 소수 쌍을 초기화한다
3. 이때, 두 소수의 차이가 최소가 되는 경우를 찾아야하므로, minDifference 변수에 최소차이값을 저장하면서 루프를 돌린다.

---

Code

package com.company.baekjoon;

import java.io.*;
import java.util.Arrays;

public class 한규호_9020 {

  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  public static void main(String[] args) throws IOException {
    int caseCnt = Integer.parseInt(br.readLine());
    int[] numbers = new int[caseCnt];
    int maxNum = 0;
    for (int i = 0; i < caseCnt; i++) {
      numbers[i] = Integer.parseInt(br.readLine());
      if (maxNum < numbers[i]) {
        maxNum = numbers[i];
      }
    }
    boolean[] isPrime = new boolean[maxNum + 1];
    Arrays.fill(isPrime, true);
    for (int i = 2; i * i < maxNum; i++) {
      if (isPrime[i]) {
        for (int j = i * 2; j < maxNum + 1; j += i) {
          isPrime[j] = false;
        }
      }
    }
    for (int number : numbers) {
      printGoldbachPartition(number, isPrime);
    }
    bw.close();
  }

  static private void printGoldbachPartition(int n, boolean[] isPrime) throws IOException {
    int minDifference = 9996;
    int primeA = 0;
    int primeB = 0;
    for (int i = 2; i < n; i++) {
      if (isPrime[i]) {
        int j = n - i;
        if (isPrime[j]) {
          int difference = Math.abs(i - j);
          if (minDifference > difference) {
            primeA = i;
            primeB = j;
            minDifference = difference;
          }
        }
      }
    }
    bw.write(primeA + " " + primeB + "\n");
  }
}

---

문제 링크