kingsubin

import java.io.*;
import java.util.StringTokenizer;

// # 골드바흐의 추측
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int a, b, n;
    static boolean[] prime = new boolean[1000001];

    public static void main(String[] args) throws IOException {
        for (int i = 2; i < prime.length; i++) {
            prime[i] = true;
        }
        for (int i = 2; i*i < prime.length; i++) {
            for (int j = i*2; j < prime.length; j+=i) {
                prime[j] = false;
            }
        }


        while ((n = Integer.parseInt(br.readLine())) != 0) {
            for (int i = 2; i <= n; i++) {
                if (prime[i]) {
                    a = i;
                    b = n-a;
                }

                if (prime[b]) {
                    bw.write(n + " = " + a + " + " + b +"\n");
                    break;
                }
            }
        }

        bw.flush();
        bw.close();
    }
}

 

- 에라토스테네스의 체 알고리즘 -> 소수를 prime에 체크해놓음

- n을 만드는 방법이 여러가지라면 a,b의 차이가 가장 큰 것을 출력해야한다

- a를 prime배열의 2부터 시작해서 가장 작은수를 찾고, b = n -a 로 표현

- 만약에 여기서 b도 소수일경우 출력후 break

- 애초에 10^18까지 증명이 완료되었으니 나타낼수 없는경우는 표시하지 않았음