(C++) - 백준(BOJ) 9020번 : 골드바흐의 추측 답

www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

아리스토테네스의 체를 이용해 푸는 문제였습니다.

 

풀이방법 

 1. 아리스토테네스의 체로 소수가 아닌 수들을 체크한다.

 2. 서로 다른 두 소수들 중 가장 작은 차이가 나는 경우는 두 소수가 각각 n/2일 경우다. 따라서 차이가 가장작은 n/2를 중앙으로 i, n-i를 차례대로 보면서 정답을 갱신해나가면 차이가 최소인 두 소수가 나온다.

 

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

void aristotle(int checkPrime[10001]){
    for(int i = 2; i <= 10000; i++){
        if(!checkPrime[i]) 
            for(int j = i+i; j<10000; j+=i) 
                checkPrime[j] = 1;
    }
}

void printSmallestGap(int n, int checkPrime[10001]){
    pair <int, int> ans(0,0x7f7f7f7f);
    for(int i = 0; i <= n/2; i++){
        if(!checkPrime[i] && !checkPrime[n-i]) {
            if(abs(ans.first-ans.second) > n-i-i){
                ans.first = i;
                ans.second = n-i;
            }
        }
    }
    cout << ans.first << ' ' << ans.second << '\n';
}

int main(){
    fastio;
    int n,t;
    int checkPrime[10001];
    aristotle(checkPrime);

    cin >> t;
    while(t--){
        cin >> n;
        printSmallestGap(n, checkPrime);
    }
}