[BOJ 6588 // C++] 골드바흐의 추측

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 6588번 문제인 골드바흐의 추측이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

골드바흐의 추측은 지금까지 해결되지 않는 정수론의 추측 중 하나로, 그 명제의 단순함에 지금까지 많은 사람들이 증명을 시도해온 문제이다.

단지 지금까지 알려져 있는 내용은 상당히 큰 수까지 이 골드바흐의 추측이 성립한다는 것 뿐이다.

물론, 문제에서 주어진 범위인 100만 이하의 수에서는 당연히 이 추측이 성립한다.

따라서, 문제의 조건 중 추측이 틀렸다는 것을 출력하는 부분은 구현할 필요가 없다.

 

한번에 계산해야 할 테스트케이스가 많으므로, 에라토스테네스의 체(Sieve of Eratosthenes)를 이용하여 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin; using std::cout;

bool sieve[1000001];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 2;i <= 1000;i++) {
        if (sieve[i] == 0) {
            for (int j = i * i;j <= 1000000;j += i) sieve[j] = 1;
        }
    }
    int N; cin >> N;
    while (N!=0) {
        for (int i = 3;i <= 1000;i++) {
            if (!sieve[i] and !sieve[N - i]) {
                cout << N << " = " << i << " + " << N - i << '\n'; break;
            }
        }
        cin >> N;
    }
    return 0;
}