[JAVA] 백준 알고리즘 17103번 (골드바흐 파티션)

문제

---

이번에 다뤄볼 문제는 17103번 문제 '골드바흐 파티션'입니다.

골드바흐의 추측(Goldbach's conjecture)이란 문제에서 설명하듯, 2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다는 것입니다.

 

이 문제를 풀기위해 우리는 "에라토스테네스의 체"를 사용할건데요. 이전에 올려뒀던 소수찾기 문제를 참고하셔도 좋습니다. 에라토스테네스의 체에 대해 아직 낯설거나 정확한 이해를 못하셨다면 위키백과에 잘 설명되어있으니 한번 정리하고 오시길 바랍니다.

 

이 문제에서 주의해야 할 점은 소수를 나타내는 Set을 미리 메모리에 올려놓고 재사용을 해야 타임아웃에 걸리지 않습니다.

입력이 6이 주어진다면 {2,4} {3,3}의 소수 조합이 있고

입력이 10이 주어진다면 {3,7} {5,5}

입력이 12가 주어진다면 {5,7} {7,5}

이렇게 소수조합이 생기게 됩니다. 다만, 12의 경우 5,7의 순서만 다른 경우기 때문에 한가지 경우로 생각해야 합니다.

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

코드(JAVA)

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        var isNotPrimes = getIsNotPrimeArray();
        Scanner sc = new Scanner(System.in);

        var tc = sc.nextInt();
        for (int i = 0; i < tc; i++) {
            var num = sc.nextInt();
            int result = 0;

            for (int j = 2; j <= num / 2; j++) {
                if (!isNotPrimes[j] && !isNotPrimes[num - j]) {
                    result++;
                }
            }
            System.out.println(result);
        }
    }

    private static boolean[] getIsNotPrimeArray() {
        boolean[] arr = new boolean[1000001];

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

 

17103번: 골드바흐 파티션