골드바흐의 추측 (feat. 백준, 6588번)

골드바흐의 추측
https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <cmath>
#include <string.h>
#define MAX_VALUE       1000000
using namespace std;
bool arr[MAX_VALUE];
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    memset(arr, false, sizeof(arr));
    arr[0] = arr[1] = true;
    register int e = sqrt(MAX_VALUE);
    for(register int i = 2, j; i <= e; ++i)
        if(!arr[i])
            for(j = i << 1; j < MAX_VALUE; j += i)
                arr[j] = true;
    register int N;
    while(1){
        cin >> N;
        if(N == 0)
            break;
        register int i = 0;
        while(++i){
            if(N - i < i){
                i = -1;
                break;
            }
            if(!arr[i] && !arr[N - i])
                break;
        }
        if(i < 0)
            cout << "Goldbach\'s conjecture is wrong.";
        else
            cout << N << " = " << i << " + " << N - i;
        cout << "\n";
    }
    return 0;
}
// *&)*@*

 

1. "에라토스테네스의 체" 를 통해 1000000 이하의 소수를 모두 구합니다.
2. i 와 N-i가 소수인 경우를 구하고 아닌 경우 i를 증가시킵니다.
   예로 N = 8인 경우, i = 2일때 2는 소수지만 8-2=6은 소수가 아닙니다. 따라서 ++i를 통해 i = 3일때 3은 소수고 8-3=5도 소수이므로 답이 되겠습니다.