백준 14905 소수 4개의 합

 

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

14905번: 소수 4개의 합

 

골드바흐의 추측을 이용하는 문제였습니다. 

골드바흐의 추측은 "2보다 큰 짝수는 소수 두개의 합으로 나타낼 수 있다."입니다.

우리는 8이상의 어떤 자연수가 주어져도 임의의 소수 두개를 빼서 짝수로 만들 수 있습니다. 

짝수일경우 소수 2 2를 빼면 되고 홀수일경우 소수 2 3을 빼면 됩니다.

소수 4개의 합중 2개의 합을 구했으니 나머지는 미리 에라토스테네스의 체로 소수를 구하고 O(N/2)반복문으로 두개의 합을 만들어 두개가 소수인지 검증만 하면됩니다.

 

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<map>
#include<stack>
using namespace std;
bool pn[50000000];
int main(){
    for(int x=2;x<=25000000;x++){
        if(pn[x]) continue;
        for(int y=x*2;y<=50000000;y+=x){
            pn[y]=true;
        }
    }
    int N;
    while(cin>>N){
        if(N<8){
            cout<<"Impossible.\n";
            continue;
        }
        if(N%2==0){
            cout<<"2 2 ";
            N-=4;
        }
        else{
            cout<<"2 3 ";
            N-=5;
        }
        if(N==4){
            cout<<"2 2\n";
            continue;
        }
        for(int x=3;x<=N/2;x+=2){
            if(!pn[x] && !pn[N-x]){
                cout<<x<<" "<<N-x<<'\n';
                break;
            }
        }
    }
}