[백준] 6588번 골드바흐의 추측: 에라토스테네스의 체 활용하여 해결 : Programming Story

1. 문제

1) 링크

www.acmicpc.net/problem/6588

2) 문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

3) 입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

4) 출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

더 자세한 문제의 조건을 알아보기 위해서는 위의 링크를 클릭해보자.

2. 풀이

이 문제를 풀기 위해서는 '에라토스테네스의 체'라는 방법을 알면 좋다.

에라토스테네스의 체 방법을 활용해서 이 문제를 풀 수 있다.

먼저 이 문제를 풀기 위해 MAX로 주어진 1000000까지 에라토스테네스의 체 방법을 사용하여서 가능한 소수 리스트를 모두 다 구해보자. 계속 add를 할 것이기 때문에 ArrayList를 사용했다. 배열을 사용하면 정확한 사이즈를 알 수 없기 때문에 for문을 더 오래 돌려야 하는 단점이 있다.

에라토스테네스의 체 방법을 사용한 코드는 아래와 같다.

ArrayList<Integer> prime = new ArrayList<Integer>();
        check[0]=true;
        check[1]=true;
        for(int i=2; i*i<=MAX; i++){
            if (check[i]) continue;
            prime.add(i);
            for(int j=2*i; j<=MAX; j+=i){
                check[j]=true;
            }
        }

이후 소수를 다 구해주었다면 이 문제는 이런 식으로 풀면 된다.

예를 들어 N= A + B 라고 되어 있으면 A를 Prime ArrayList 중 하나의 요소라고 보는 것이다. (prime arraylist를 돌면서 하나를 가져오는 식으로) 그러면 B는 N-A가 되는데, 만약 N-A 또한 소수이면 소수 두개로 합을 나타낼 수 있는 것이다. (A는 이미 prime 의 list에서 가져온 수이기 때문이다)

그리고 우리는 이미 에라토스테네스의 체 방법을 사용하면서 해당 숫자가 소수인지 아닌지를 저장하는 boolean 배열 check를 사용했기 때문에 N-A가 소수인지 아닌지는 해당 배열만 검사하면 된다.

3. 코드

에라토스테네스의 체로 소수를 구하고 해당 방법으로 문제를 푼 전체 코드는 아래와 같다.

import java.util.*;

public class Main{
    public static final int MAX = 1000000;
    public static void main(String[] args){
        boolean[] check = new boolean[MAX+1];
        ArrayList<Integer> prime = new ArrayList<Integer>();
        check[0]=true;
        check[1]=true;
        for(int i=2; i*i<=MAX; i++){
            if (check[i]) continue;
            prime.add(i);
            for(int j=2*i; j<=MAX; j+=i){
                check[j]=true;
            }
        }
        Scanner sc=new Scanner(System.in);
        while (true){
            int n=sc.nextInt();
            if (n==0) break;
            boolean find=false;
            for(int i=0; i<prime.size(); i++){
                int tmp=prime.get(i);
                if (!check[n-tmp]){
                    find=true;
                    System.out.println(n+" = "+tmp+" + "+(n-tmp));
                    break;
                }
            }
            if (!find){
                System.out.println("Goldbach's conjecture is wrong.");
            }
        }
    }

마지막에 덧셈 조합을 찾지 못했다면 "Goldbach's conjecture is worng."을 출력해달라고 했으므로 find라는 boolean 값을 하나 만들어주어서 그것이 for문을 돌았는데도 false이면 찾지 못했다는 뜻이므로 그런식으로 알고리즘을 구상하면 된다.

BOJ에서는 마지막 줄을 출력하지 않아도 맞는 것으로 나오는 것 같은데 (테스트케이스에 없는 것 같다 : 사실 골드바흐의 추측이 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다 라는 것이기 때문) 정확하게 문제를 풀려면 마지막 출력라인도 적어주어야 한다.