[백준] 9020

 

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

골드바흐 추측인 2보다 큰 짝수를 소수 2개로 나타내는 문제이다. 

에라토스테네스 체로 체를 만들어놓고, n/2에서 양쪽으로 두 포인터를 보내면서 n과 두 포인터의 값을 비교하면서 두 값을 찾았다.

체를 매 T마다 무식하게 구했는데, 더 나은 방법이 있을 것 같다

 

코드

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

int T;
vector<int> sieve;

void build_sieve(int n){
    sieve.clear();
    if(n <= 1) return;
    sieve.reserve(n+1);
    for(int i=2; i<=n; i++)
        sieve[i] =1;

    for(long long i=2; i*i<=n; i++){
        if(sieve[i])
            for(long long j=i*i; j<=n; j += i)
                sieve[j] = 0;
    }
}
int main(){
    scanf("%d", &T);
    int n;
    int lp, rp;
    while(T--){
        scanf("%d", &n);
        build_sieve(n);
        lp=rp=n/2;

        while(2<=lp && rp <= n){
            if(!sieve[lp]){lp--; continue;}
            if(!sieve[rp]){rp++; continue;}

            int result=n-(lp+rp);
            if(result<0){ lp--; continue; }
            else if(result>0){ rp++; continue; }
            else{ printf("%d %d\n", lp, rp); break; }
        }
    }
}