ゴールドバッハの予想
Summation of Four Primes
http://acm.uva.es/p/v101/10168.html
自然数Nを任意の4つの素数の和で表せという問題．N<=10^7なので，brute-forceだとTLE．
この問題はゴールドバッハの予想を使う．多くの場合ゴールドバッハの予想とは，
4以上の任意の偶数は，2つの素数の和で表せる
と言われるようである．
ここでこの予想から以下のように拡張する．4以上の任意の偶数を表す素数のペアそれぞれについて，それに要素として2を加えたものと，3を加えたものを考える．例えば，4を表す(2,2)というペアから，(2,2,2)と(2,2,3)という集合を作る．つまり，3つの素数の要素からなる集合がたくさんできることになる．これらの集合のそれぞれの合計値は，6以上の自然数のどれかであるから，
と言える．同様に，これらの3つの素数の集合それぞれに要素として2を加えると，
と言える．
ということで問題の解法に戻ると，N>=8のとき，かつ，その時に限って，Nを4つの素数の和で表せることが分かった．しかも4つのうち2つは，Nが偶数か奇数かによって勝手に決まるから，実際には2つの素数の組み合わせだけを調べれば良い．
