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

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

6588번: 골드바흐의 추측

---

 

해석 및 팁

 

---

 

이 문제는 에라토스테네스의 채를 활용하는 문제입니다. n의 범위가 100만이므로 먼저 100까지의 소수를 구해놓은 뒤 주어진수를 반복문을 통해 두 수의 합으로 나타내면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();

    boolean[] arr= new boolean[1000001];

    arr[0] = true;
    arr[1] = true;
    for(int i = 2; i * i <= 1000000; i++) {
      if(arr[i] == true) continue;
      for(int j = i * i; j <= 1000000; j += i) arr[j] = true;
    }

    while(true) {
      int n = sc.nextInt();
      if(n == 0) break;
      int a = 2;
      int b = n - 2;
      while(true) {
        if(arr[a] == false && arr[b] == false) {
          sb.append(n+" = "+a+" + "+b).append("\n");
          break;
        }
        a++;
        b--;
      }
    }

    System.out.println(sb);
  }
}