#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;
}
廣告

Comment

There is no comment on this post. Be the first one.

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: