BOJ 6588 · 골드바흐의 추측

알고리즘 분류 : 수학  

골드바흐의 추측(Goldbach's conjecture)이란, 2보다 큰 모든 짝수는 두 개의 소수의 합으로 나타낼 수 있다는 추측을 말한다.

• 우선 2부터 1,000,000까지의 모든 소수를 에라토스테네스의 체로 구한다. 참조
• 입력 N에 대하여 위에서 구한 소수를 2부터 순서대로 A라고 정한다.
• B = N-A인 소수가 존재하는지 확인하기 위해서, 위에서 구한 소수의 집합에서 확인한다.
• 존재하면, N = A + B를 출력하고 마친다.

참고사항

• 10^18 이하의 숫자에 대해서는 골드바흐의 추측이 참인 것이 보증되므로, "Goldbach's conjecture is wrong."을 출력할 필요는 없다.
• 에라토스테네스의 체를 통해 구한 소수를 별도의 배열로 생성하여 범위를 줄이면 시간을 줄일 수 있다.
• B-A 값이 가장 큰 것을 출력하는 것이므로, A와 B를 처음 찾자마자 break 하면 된다.

---

C++ 소스코드

#include <cstdio>

const int MAX = 1000000;
bool prime[MAX+1];

int main() {
    for (int i=2; i*i<=MAX; i++) {
        if (!prime[i]) {
            for (int j=(i*i)%MAX; j<=MAX; j+=i) {
                prime[j] = true;
            }
        }
    }
    while (true) {
        int n;
        scanf("%d", &n);
        if (n == 0) break;
        for (int i=2; i<=MAX; i++) {
            if (!prime[i]) {
                int j = n-i;
                if (!prime[j]) {
                    printf("%d = %d + %d\n", n, i, j);
                    break;
                }
            }
        }
    }
    return 0;
}

---

Python 3 소스코드

MAX = 1000000
prime = [False for _ in range(MAX+1)]

for i in range(2, MAX+1):
    if i*i > MAX:
        break
    if prime[i] is False:
        for j in range(i*i, MAX+1, i):
            prime[j] = True

while True:
    n = int(input())
    if n is 0:
        break
    for i in range(2, MAX+1):
        if prime[i] is False:
            j = n - i
            if prime[j] is False:
                print(n, "=", i, "+", j)
                break

---

참고

• 백준 온라인 저지 : BOJ 6588
• 위키피디아 : 골드바흐의 추측
• 위키피디아 : 에라토스테네스의 체