[백준 6588] 골드바흐의 추측, C++

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

6588번: 골드바흐의 추측

 본 문제는 1998 University of Ulm Local Contest G번 문제다. 1742년 골드바흐는 다음과 같은 추측을 하였다. '4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.'  골드바흐의 추측의 자세한 내용은 링크를 참고 바란다. 문제에서 입력의 최대 크기가 1,000,000 이므로 에라토스테네스의 체를 이용하면 빠르게 처리할 수 있다.

1. 에라토스테네스의 체로 최대 입력까지의 소수를 구한다.
2. 2부터 골드바흐의 추측을 확인하고 맞으면 break

#include <cstdio>
 
using namespace std;
 
int main() {
    bool chk[1000001];
    chk[0] = true;
    chk[1] = true;
    for (int i = 2; i <= 1000000; i++) {
        if (!chk[i]) {
            for (int j = i*2; j <= 1000000; j += i) {
                chk[j] = true;
            }
        }
    }
    int n;
    while (true) {
        scanf("%d", &n);
        if (n == 0) return 0;
        for (int i = 2; i <= n; i++) {
            if (!chk[i] && !chk[n-i]) {
                printf("%d = %d + %d\n", n, i, n-i);
                break;
            }
        }
    }
}