BOJ - 골드바흐의 추측(9020)

실버1 : 수학 문제이다.

생각

소수 구하는 알고리즘인 에라토스테네스의 체를 사용하면 간단히 풀 수 있다. 이 때, 시간제한 때문에 구한 소수를 담아두는 것이 좋다.

Code

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAX 10000
using namespace std;
bool isPrime[MAX+1];
 
 
void SeiveofEratosThenes(){
    fill(isPrime+2, isPrime+MAX+1, true);
    for (int i = 2; i*i <= MAX; i++) {
        if (isPrime[i] == false) continue;
        for (int j = i*i; j <= MAX; j+=i) {
            isPrime[j] = false;
        }
    }
}
 
void solve(int N){
    vector<int> prime;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) prime.push_back(i);
    }
    int size = int(prime.size());
    int a = -100000, b = 100000;
    for (int i = 0; i <= size; i++) {
        for (int j = i; j <= size; j++) {
            if (prime[i]+prime[j] == N) {
                if (prime[j]-prime[i] < b-a) {
                    a = prime[i]; b = prime[j];
                }
            }
        }
    }
    cout << a << " " << b << '\n';
}
 
 
int main(){
    SeiveofEratosThenes();
    int T;
    cin >> T;
    for (int tc = 0; tc < T; tc++) {
        int N;
        cin >> N;
        solve(N);
    }
    return 0;
}
 

Reference

• 백준(9020번) - 골드바흐의 추측