골드바흐의 추측

23 June 2019

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

이번은 n이 주어졌을 때, 두 소수의 합으로 n을 표현하는 문제를 풀어보도록 하겠습니다.

import java.util.Scanner;

public class Main {

    private static int[] primeNumbers = new int[10001];

    public static void main(String args[]) {

        primeNumbers[1] = 1;
        for (int i = 2; i < primeNumbers.length - 1; i++) {
            int k = 2;
            while (true) {
                if (k * i > primeNumbers.length - 1) {
                    break;
                }
                primeNumbers[k * i]++;
                k++;
            }
        }

        Scanner sc = new Scanner(System.in);

        int size = sc.nextInt();

        for (int i = 0; i < size; i++) {
            int val = sc.nextInt();
            int ret = 0;
            for (int k = 2; k < (val / 2) + 1; k++) {
                if ((primeNumbers[k] == 0) && (primeNumbers[val - k] == 0)) {
                    ret = k;
                }
            }
            System.out.println(ret + " " + (val - ret));
        }
    }
}

이번 문제에서는 들어오는 값의 범위가 10,000까지의 범위이므로 해당 값까지의 모든 소수를 구해놓습니다.
두 개의 소수의 합이 하나의 값이 되므로 두 소수의 차이가 가장 작은 경우는 해당 소수가 들어오는 값/2 인 경우입니다.
따라서, 소수는 들어오는 값 val/2 까지의 소수를 조회해 소수값 ret과 val-ret의 값이 소수인 경우를 저장합니다.
해당 수 중에 가장 큰 값을 return해주도록 합니다.