백준 17103번 [골드바흐 파티션](C++) -yes6686- 티스토리

백준 문제 풀이: 17103 (골드바흐 파티션)

---

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

문제 설명:

짝수 x를 두 소수의 합으로 나타내는 경우의 수를 구하는 문제입니다. 이때, 두 소수의 합을 **골드바흐 파티션**이라 부르며, 두 소수의 순서는 고려하지 않습니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int p[1000001]; // 소수 판별을 위한 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    // 에라토스테네스의 체를 이용한 소수 판별
    for (int i = 2; i <= 1000000; i++) {
        p[i] = i; // 초기화
    }
    for (int i = 2; i * i <= 1000000; i++) {
        if (p[i] == 0) continue; // 소수가 아니면 건너뜀
        for (int j = i * i; j <= 1000000; j += i) {
            p[j] = 0; // 소수의 배수는 소수가 아님
        }
    }

    int T;
    cin >> T; // 테스트 케이스 수 입력

    while (T--) {
        int x;
        cin >> x; // 짝수 입력
        int cnt = 0; // 골드바흐 파티션 수 카운트

        // x를 두 소수의 합으로 나타내는 경우의 수 확인
        for (int i = 2; i <= x / 2; i++) {
            if (p[i] && p[x - i]) { // i와 x-i가 모두 소수인 경우
                cnt++;
            }
        }
        cout << cnt << '\n'; // 결과 출력
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 에라토스테네스의 체: - **소수 판별**을 위해 에라토스테네스의 체를 사용하여 2 ~ 1000000까지의 소수를 미리 구합니다. - 소수가 아닌 숫자는 배열 p에서 0으로 표시됩니다.
• 골드바흐 파티션 계산: - 주어진 짝수 x에 대해, i와 x - i가 모두 소수인지 확인합니다. - 탐색 범위는 **i ≤ x / 2**로 제한합니다. - 조건을 만족하면 카운트 cnt를 증가시킵니다.

시간 복잡도 분석

• **에라토스테네스의 체:** - 소수를 구하는 데 걸리는 시간 복잡도는 **O(N log log N)**입니다.
• **골드바흐 파티션 탐색:** - 각 테스트 케이스마다 **O(N / 2)**입니다.
• 최종적으로 전체 시간 복잡도는 **O(T ⋅ N / 2 + N log log N)**입니다.

---

결과

주어진 짝수를 두 소수의 합으로 나타내는 **골드바흐 파티션의 개수**를 출력합니다.

• 입력 예시:

  3  
  8  
  10  
  12

• 출력 예시:

  1  
  2  
  1

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!