[알고리즘] 백준 9020번 골드바흐의 추측 (에라토스테네스의 체, 소수 알고리즘)

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

문제

1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

입력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

제한

4 ≤ n ≤ 10,000

예제 입력 1

3
8
10
16

에제 출력 1

3 5
5 5
5 11

Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        int[] numArray = new int[T];


        boolean[] prime = new boolean[10001];

        prime[0] = prime[1] = true;

        for(int i = 2; i <= Math.sqrt(prime.length); i++){

            if(prime[i] == true){
                continue;
            }

            for(int j = i*i; j < prime.length; j= j+i){
                prime[j] = true;
            }
        }

        for(int i = 0; i < numArray.length; i++){
            numArray[i] = Integer.parseInt(br.readLine());
        }

        for (int num : numArray) {

            int x = num / 2;
            int y = num / 2;

            while(true){
                if(!prime[x] && !prime[y]){
                    System.out.println(x + " " + y);
                    break;
                }
                x--;
                y++;
            }

        }

    }
}

Point

일단 소수 구하는 알고리즘을 알아야 풀 수 있다. 에라토스테네스의 체라는 알고리즘이 존재한다.

해당 알고리즘은 2부터 시작(0 과 1은 소수가 아님)하여 구하려는 숫자의 제곱근(루트)까지의 모든 숫자의 곱들을 제외한다.

예를 들어 2로 시작하여 2를 제외한 2의 배수인 4, 6, 8 ... 3을 제외한 3의 배수 6, 9, 12 ... 이런식으로 소수가 아닌 숫자를 지워나가는 방식이다.

for(int i = 2; i <= Math.sqrt(prime.length); i++){

            if(prime[i] == true){
                continue;
            }

            for(int j = i*i; j < prime.length; j= j+i){
                prime[j] = true;
            }
        }

https://st-lab.tistory.com/81

에라토스테네스의 체에 대한 더 자세한 설명은 위의 블로그에 매우 잘 나와있다.

그 다음으로 이 문제를 풀기 위해서 두 소수의 차가 가장 작은 값을 도출해내는 것이다.

예를 들어 number=10일 경우

10 이하의 소수는 2, 3, 5, 7 로 총 4개가 존재하는데

3과 7의 조합으로도 10이 만들어지고, 5와 5의 조합으로도 10이 만들어지게 된다.

하지만 문제에서 원하는 답은 5, 5이다.

들어오는 수는 무조건 짝수이며, 배열은 순서대로 나열되어 있기 때문에 정 가운데

즉, 숫자의 절반부터 시작하며 탐색해 나아가면 위와 같은 코드로 구현이 가능하다.

소수 구하는 문제에서 가장 중요한 부분은 위으 소수 알고리즘을 이해하고 익히는 것인것 같다.

시간 복잡도가 최대 O(N²) 부터 시작하여

에라토스테네스의 체 알고리즘을 사용할 경우 O(Nlog(log N)) 까지 많이 줄일 수 있기 때문이다.