백준 6588 - 골드바흐의 추측

문제

 

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

6588번: 골드바흐의 추측

 

 

풀이

 

에라토스테네스의 체를 이용해서 1000000 이하의 소수를 먼저 구한다. 에라토스테네스의 체를 이용하면 c 배열에 각 수가 소수인지 아닌지에 대한 정보가 저장이 된다. 

 

주어진 짝수 n이 두 개의 홀수 소수로 이루어지는지 알아보기 위해서, i = 3 부터 2칸씩 증가시키면 된다. 이때 i와 (n - i) 둘 다 소수일 때 정답이 된다.

 

 

코드

 

#include <iostream>
 
using namespace std;
 
const int MAX = 1000000;
 
int n;
bool c[MAX + 1];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    for (int i=2; i<=MAX; i++)
    {
        if (!c[i])
            for (int j=i+i; j<=MAX; j+=i) c[j] = true;
    }  
 
    while(true)
    {
        cin >> n;
        if (!n) break;
        bool fail = true;
        for (int i=3; i<MAX; i+=2)
        {
            if (!c[i] && !c[n - i])
            {
                cout << n << " = " << i << " + " << n - i << '\n';
                fail = false;
                break;
            }
        }
        if (fail) cout << "Goldbach's conjecture is wrong." << '\n';
    }
 
   
    return 0;
}