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

9020번: 골드바흐의 추측 링크

코드

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

bool judge_prime(int num){
    if(num == 1) return 0;
    for(int i = 2; i <= sqrt(num); i++)
        if(num % i == 0) return 0;

    return 1;
}


int main(){

    vector<int> prime_vec;
    bool arr[10001] = {0,};
    //10000까지의 소수.
    for(int i=2; i < 10001; i++){
        if(arr[i] == 1) continue;
        if(judge_prime(i)){
            prime_vec.push_back(i);
            for(int j = 2; i*j < 10001; j++){
                arr[i * j] = 1;
            }
        }
    }

    int t, n;
    int answer[2] = {0,};
    cin >> t;

    for(int k = 0; k < t; k++){
        int min_sub = 20000;
        cin >> n;
        for(int l = 0; prime_vec[l] < n; l++){
            for(int m = 0; prime_vec[l] + prime_vec[m] <= n; m++){
                if(prime_vec[l] + prime_vec[m] == n){
                    if(abs(prime_vec[l] - prime_vec[m]) < min_sub){
                        min_sub = abs(prime_vec[l] - prime_vec[m]);
                        answer[0] = prime_vec[l];
                        answer[1] = prime_vec[m];}
                }
            }
        }
        if(answer[0] > answer[1]){
            int temp = answer[0];
            answer[0] = answer[1];
            answer[1] = temp;
        }
        cout << answer[0] << " " << answer[1] << "\n";

    }


}

사견

특별히 할 말이 없는 문제이다.
이전에 몇 번 풀었던 소수 문제이기 때문.
에라토스테네스의 체를 활용하여 풀면 되는 간단한 문제이다.

2581번: 소수 문제풀이
이전에 내가 풀었던 이 포스팅을 보면 이해에 조금 도움이 될 수 있다.

에라토스테네스의 체 위키백과