[BOJ 9020 // C++] 골드바흐의 추측

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 9020번 문제인 수열과 헌팅이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

골드바흐의 추측은 유명한 미해결문제로, 2를 제외한 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 내용을 담고 있다. 적당히 큰 수의 범위 내에서는 모든 짝수가 두 소수의 합으로 나타내짐이 알려져있다. 이 문제에서는 10000 이하의 (2가 아닌) 짝수를 두 "차이가 가장 적은" 소수의 합으로 나타내야 한다.

 

차이가 가장 적은 소수의 쌍을 찾기 위해 주어진 짝수의 절반값서부터 탐색해나가자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

bool sieve[10001];

int main()
{
    for (int i = 2;i < 10001;i++) {
        sieve[i] = true;
    }
    for (int i = 2;i <= 100;i++) {
        if (sieve[i]) {
            for (int j = i * i;j < 10001;j += i) {
                sieve[j] = false;
            }
        }
    }

    int n;
    cin >> n;
    int x, pt;

    for (int i = 0;i < n;i++) {
        cin >> x;
        x /= 2;
        pt = 0;
        while (!sieve[x + pt] or !sieve[x - pt]) {
            pt++;
        }
        cout << x - pt << ' ' << x + pt << "\n";
    }

    return 0;
}