백준 6588번 [골드바흐의 추측](C++) -yes6686- 티스토리

백준 문제 풀이: 6588 [골드바흐의 추측]

---

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

문제 설명:

골드바흐의 추측에 따르면 2보다 큰 모든 짝수는 두 개의 소수의 합으로 표현될 수 있습니다. 이 문제에서는 주어진 짝수 n에 대해 두 소수의 합으로 나타내는 방법을 찾고, 이를 출력하는 것이 목표입니다.

만약 표현할 수 없는 경우 "Goldbach's conjecture is wrong."을 출력해야 합니다.

---

문제 해결 코드

#include <iostream>
#include <vector>
#define MAX 1000001
using namespace std;

int arr[MAX]; // 소수 판별 배열
vector<int> primes; // 소수 목록

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

    // 에라토스테네스의 체를 사용하여 소수 구하기
    for (int i = 2; i < MAX; i++) {
        arr[i] = i;
    }

    for (int i = 2; i * i < MAX; i++) {
        if (arr[i] == 0) continue;
        for (int j = i * i; j < MAX; j += i) {
            arr[j] = 0;
        }
    }

    // 소수 목록 저장
    for (int i = 2; i < MAX; i++) {
        if (arr[i]) primes.push_back(i);
    }

    // 입력 처리
    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;

        bool found = false;

        for (int i = 0; i < primes.size(); i++) {
            if (arr[n - primes[i]]) {
                cout << n << " = " << primes[i] << " + " << (n - primes[i]) << '\n';
                found = true;
                break;
            }
        }

        if (!found) {
            cout << "Goldbach's conjecture is wrong.\n";
        }
    }

    return 0;
}

예제 입력:

8
20
42
0

예제 출력:

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

---

코드 설명

• 핵심 알고리즘: 에라토스테네스의 체를 사용하여 1,000,000까지의 소수를 미리 구한 후, 주어진 n에 대해 두 소수의 합으로 표현하는 방법을 찾습니다.
• 구현 세부사항:
  • 에라토스테네스의 체를 사용하여 소수를 미리 계산합니다.
  • 입력된 짝수 n에 대해 n - 소수가 소수인지 확인합니다.
  • 가장 작은 소수부터 탐색하므로, 첫 번째로 발견되는 조합이 정답입니다.
• 시간 복잡도: O(N log log N) (소수 판별) + O(N) (짝수에 대한 소수 탐색)

---

결과

입력된 짝수를 두 개의 소수의 합으로 나타내는 가장 작은 조합을 찾아 출력합니다. 골드바흐의 추측을 검증하는 대표적인 문제로, 에라토스테네스의 체를 활용한 최적화된 소수 탐색을 연습하기에 적합한 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!