[백준/C++] 9020번: 골드바흐의 추측

문제

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

---

문제 요약

골드바흐의 추측이란 유명한 정수론의 미해결 문제이다.

 

2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다.

이러한 수를 골드바흐 수라고 한다.

또, 짝수를 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다.

 

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력한다.

 

+ 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우, 두 소수의 차이가 가장 작은 것을 출력한다.

---

코드

#include <iostream>
#include <vector>

using namespace std;

int T;

// arr[i]가 true라면, i는 소수
bool arr[10010];
vector<int> v;

void gold(int n) {
    int left = 0;
    int right = v.size() - 1;

    int res_left = 0;
    int res_right = 0;

    // 투포인터
    while (left <= right) {
        int sum_lf = v[left] + v[right];

        if (sum_lf == n) {
            res_left = v[left];
            res_right = v[right];
            left++;
            right--;
        }
        else if (sum_lf < n) {
            left++;
        }
        else {
            right--;
        }
    }

    cout << res_left << " " << res_right << "\n";
}

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for (int i = 0; i <= 10000; i++) {
        arr[i] = true;
    }

    // 에라토스테네스의 체 알고리즘
    for (int i = 2; i * i <= 10000; i++) {
        // 소수가 이미 아니라면, 건너뛰기
        if (!arr[i]) continue;

        int j = 2;
        while (i * j <= 10000) {
            arr[i * j] = false;
            j += 1;
        }
    }

    for (int i = 0; i < 10000; i++) {
        if (arr[i]) v.push_back(i);
    }


    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        gold(n);

    }

    return 0;
}

---

코드 설명

1. 에라토스테네스의 체 알고리즘을 활요하여 10000까지 수 중 소수들의 리스트를 벡터 v에 저장한다.

 

2. 입력 받은 수 n에 대해 투포인터 알고리즘을 통해 골드바흐 파티션을 출력한다.

 

투포인터 알고리즘에서 두 포인터가 가리키는 소수의 합이 n이어도, 차이가 작은 파티션이 존재할 수 있으므로, left, right 포인터를 한 칸씩 움직여 계속 탐색한다.

---

고찰

오랜만에 에라토스테네스의 체 알고리즘을 구현하려 하니, 까먹어서 시간이 좀 걸렸다.

 

복습하자!