문제 푼 날짜 : 2021-10-11

문제

문제 링크 : https://www.acmicpc.net/problem/6588

접근 및 풀이

소수를 구할줄 알아야 하는 문제였다.
소수는 에라토스테네스의 체를 이용하여 구현하였고, 에라토스테네스의 체는 위키백과를 참조하였다.
최대 1000000 이내의 자연수 중에 소수를 구해준 다음, 입력받은 짝수가 n이므로 (n - 임의의 소수값) 이 소수라면, 아래의 문제의 조건을 만족할 수 있다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

코드

// 백준 6588번 : 골드바흐의 추측
#include <iostream>
#include <vector>

using namespace std;

vector<bool> check(1000001, true);
vector<int> prime;

void eratos() {
    for (int i = 2; i * i <= 1000000; i++) {
        if (check[i]) {
            for (int j = i * i; j <= 1000000; j += i) {
                check[j] = false;
            }
        }
    }
    for (int i = 2; i <= 1000000; i++) {
        if (check[i]) {
            prime.push_back(i);
        }
    }
}

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

    while (true) {
        cin >> n;
        if (n == 0) {
            break;
        }
        for (int i = 0; i < prime.size(); i++) {
            if (check[n - prime[i]]) {
                cout << n << " = " << prime[i] << " + " << n - prime[i] << '\n';
                break;
            }
        }
    }
    return 0;
}

결과

피드백

에라토스테네스의 체를 이용한 소수를 구하는 방법도 외워두면 편한 알고리즘인 것 같다.