[백준 BOJ] 17103 골드바흐 파티션 C++

백준 17103번: 골드바흐 파티션

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

17103번: 골드바흐 파티션

---

문제

예제

• 문제해석 및 풀이

 이 문제는 각 테스트 케이스 별로 짝수 N이 주어졌을 때, a + b = N 을 만족하는 두 소수 a, b 순서쌍의 개수를 구하는 문제이다. 단, 두 소수의 순서가 다른 순서쌍은 같은 파티션으로 취급한다. 문제를 풀기 위해서 에라토스테네스의 체를 이용해 소수를 판별해 주어야 한다. 에라토스테네스의 체에 대한 부분은 저번 포스팅을 참고해주기 바란다. 소수를 판별한 다음에는 골드바흐의 추측에 만족하는 골드바흐 파티션의 개수를 찾아야 한다. 코드로 구현해보면 복잡해 보이지만 어렵지 않은 코드이다.

• 참고

2024.01.31 - [백준 baekjoon] - [백준 BOJ]1929 소수 구하기 C++

 

• 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> find_prime(int n) {
    vector<bool> isPrime(n + 1, true);
    vector<int> primes;
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

int goldbach(int num) {
    vector<int> primes = find_prime(num);
    int cnt = 0;
    for (int i = 0; i < primes.size(); i++) {
        int prime = primes[i];
        int comp = num - prime;
        if (comp >= prime && binary_search(primes.begin() + i, primes.end(), comp)) {
            cnt++;
        }
    }
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int res = goldbach(n);
        cout << res << "\n";
    }
    return 0;
}

 에라토스테네스의 체를 이용하여 주어진 수보다 작은 소수들이 입력되어 있는 벡터를 생성한 다음 이를 이용해 골드바흐 파티션을 구했다. 골드바흐 파티션은 주어진 짝수에서 소수들을 차례로 빼고 보수(뺀 수)가 소수이면 cnt를 증가시켜 골드바흐 파티션의 개수를 구했다. 두 소수의 순서만 다른 것은 같은 파티션이기 때문에 보수가 소수보다 크거나 같다는 조건을 추가했다.

 

• 정리

 내가 풀었던 소수들을 다룬 문제들 중에서 가장 난이도가 높았던 문제라고 생각한다. 골드바흐 파티션을 구하기 위한 알고리즘과 에라토스테네스의 체 알고리즘을 모두 구현해야 했던 문제이다.

 궁금한 것이나 더 나은 코드 및 방법, 그리고 잘못된 것이 있다면 댓글에 남겨주시기 바란다.