백준 1153 네 개의 소수

골드바흐의 추측 : 2보다 큰 짝수는 모두 두 소수의 합으로 나타낼 수 있다.
N을 4개의 소수로 볼 수 있는가?
N이 짝수라면 -> 2 2 N1 N2 로 구분
N이 홀수라면 -> 2 3 N1 N2 로 구분

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

vector<int> primes;
vector<int> ans;

bool isPrime(int n){
  if(n<=1) return false;
  for(int i = 2; i <= int(sqrt(n)); i++){
    if(n % i == 0) return false;
  }
  return true;
}

void getPrimes(){
  //primes.resize(N+1, false);
  for(int i = 2; i <= N; i++){
    if(isPrime(i)){
      primes.push_back(i);
    }
  }
}

void input(){
  cin >> N;
}

void solve(){
  if(N%2 == 0){
    //짝수면
    ans.push_back(2);
    ans.push_back(2);
    N-=4;
  }
  else{
    ans.push_back(2);
    ans.push_back(3);
    N-=5;
  }
  bool flag = false;
  for(int i = 0; i < primes.size(); i++){
    if(isPrime(N- primes[i])){
      ans.push_back(primes[i]);
      ans.push_back(N - primes[i]);
      flag = true;
      break;
    }
  }

  if(flag){
    for(int i = 0; i < ans.size(); i++){
      cout << ans[i] << " ";
    }
  }
  else{
    cout << "-1";
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  input();
  getPrimes();
  solve();
  return 0;
}