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

6588번: 골드바흐의 추측

 

www.acmicpc.net

풀이

에라토스테네스의 체를 사용해서 소수를 모두 구한 뒤, 3부터 시작해서 수를 탐색하기 시작한다. 가장 작은 홀수 소수인 3부터 홀수만 탐색하므로 처음으로 발견되는 두 수의 차이가 가장 크다는 것을 보장할 수 있다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

bool chk[1000001];

void precalc() {
    fill(chk, chk + 1000001, true);
    chk[1] = false;
    for (int i = 1; i * i <= 1000000; i++) {
        if (!chk[i]) continue;
        for (int j = i * i; j <= 1000000; j += i) 
            chk[j] = false;        
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    precalc();
    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;
        bool find = false;
        // 3부터 시작해서 홀수만 탐색
        for (int i = 3; i < n; i += 2) {
            // i와 n-i가 모두 소수인 경우
            if (chk[i] && chk[n - i]) {
                find = true;
                cout << n << " = " << i << " + " << n - i << '\n';
                break;
            }
        }
        if (!find) cout << "Goldbach's conjecture is wrong.\n";
    }
    return 0;
}