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

난이도: Silver 1
번호: 6588
생성일: February 25, 2023 10:21 AM
알고리즘 분류: 소수 판정, 수학, 에라토스테네스의 체, 정수론
언어: C++

6588번: 골드바흐의 추측

C++

// BOJ6588 골드바흐의 추측
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool prime[1000001];

void eratosthenes(int n)
{
    memset(prime, true, n);
    for (int i = 2; i * i <= n; i++)
        if (prime[i] == true)
            for (int j = i * i; j <= n; j += i)
                prime[j] = false;
}

int main(void)
{
    eratosthenes(1000000);
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);

    int n;
    while (true)
    {
        cin >> n;
        if (!n)
            break;
        bool flag;
        for (int i = 3; i < n; i += 2)
        {
            if (prime[i] && prime[n - i])
            {
                cout << n << " = " << i << " + " << n - i << "\n";
                flag = true;
                break;
            }
        }

        if (!flag)
            cout << "Goldbach's conjecture is wrong.\n";
    }
    return (0);
}