[백준/c++] 6588번: 골드바흐의 추측

 

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

6588번: 골드바흐의 추측

 

 

이 문제는 1000000까지의 소수를 먼저 찾고 시작했다. 에라토스테네스의 체 알고리즘으로 빠르게 소수를 찾을 수 있다.

이를 벡터 v에 넣어놓고 여러 테스트 케이스 값을 받아서 답을 출력한다. 

여기서 소수 && 홀수이기 때문에 소수&&홀수의 합을 찾기 위해 for문을 돌릴 때, 1부터 시작해야 한다. v [1] = 3

v [0]는 2이므로 안됨..!

n보다 작은 값들의 합이어야 n 값이 나올 수 있으므로 n보다 작은 애들끼리의 합만 보면 되는데 그러면 v [i]의 값이 n보다 작은지 체크해야 한다. 이를 위해 v [i] < n 조건을 for문에 넣어준다. 그러고 나면 이제 합이 n인지 알 수 있다. 굳이 2중 for문으로 하지 않고, n에서 홀수이지 소수인 v [i]를 빼면 나오는 값 또한 소수인지 확인만 하면 된다. 맞다면 바로 출력! 

 

 

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
bool num[1000001];
int MAX = 1000000;
vector<int> v;

//소수 먼저 찾아놓기
void primeNum(){
    for(int i=2; i<=MAX; i++) num[i] = true;
    for(int i=2; i<=sqrt(MAX); i++){
        if(!num[i]) continue;
        for(int j=i*i; j<=MAX; j+=i) num[j] = false;
    }
    for(int i=2; i<MAX; i++) if(num[i]) v.push_back(i);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    
    primeNum();
    while(1){
        cin >> n;
        if(n==0) break;
        
        bool flag = false;
        for(int i=1; v[i] < n; i++){
            int n2 = n - v[i];
            if(num[n2]){
                cout << n << " = " << v[i] << " + " << n2 << '\n';
                flag = true;
                break;
            }
        }
        if(!flag) cout << "Goldbach's conjecture is wrong.\n";
    }
    return 0;
}