#UVa：10168－Summation of Four Primes

首先，由於 4 個數字最小一定是 2 ，所以比 8 小的數字絕對不可能拼出來。那麼等於 8 或比 8 的數字，偶數可以先拆成 2 + 2 + (N-4) ，奇數可以先拆成 2 + 3 + (N-5)，而透過哥德巴赫猜想可以知道任意數字皆可分解成兩個質數，故迴圈找出即可。

P.S. 質數表的建立可以利用篩法。

參考解法：NaiveRed’s Blog

C++(0.090)

/*******************************************************/
/* UVa 10168 Summation of Four Primes                  */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2018/10/04                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  const int N_MAX_LIMIT = 10000000;
  bool isComposite[N_MAX_LIMIT + 5] = {true, true, false};
  for(int i = 2 ; i <= N_MAX_LIMIT ; ++i){
    if(isComposite[i]) continue;

    for(int j = i+i ; j <= N_MAX_LIMIT ; j += i){
      isComposite[j] = true;
    }
  } 

  int N;
  while(scanf("%d", &N) != EOF){
    if(N < 8){
       printf("Impossible.\n");
       continue;
    }

    if(N % 2 == 0){
      printf("2 2 ");
      N -= 4;
    }
    else{
      printf("2 3 ");
      N -= 5;
    }

    for(int i = 2 ; i <= N ; ++i){
      if(!isComposite[i] && !isComposite[N-i]){
        printf("%d %d\n", i, N-i);
        break;
      }
    }
  }
  return 0;
}