41は連続する6個の素数の和で表すことのできる素数（41 = 2 + 3 + 5 + 7 + 11 + 13）である。100以下では41の持つ6連続が最長である。100万以下で最も長い連続する素数の和で表される素数を求める。
100万以下の素数の列から2つ選んで総当りで答えを求めることもできるであろう。しかしかなりの時間がかかるであろうことが予想される。単純に考えて総当りの計算量はO(n2)のオーダである。 こんなときは分割統治を考えてみるのが1つのセオリーか…？ということで、次の手順で探索してみた。
(1) 与えられた数列を2つに分割し、それぞれの数列の中で最も長い素数和を見つける (2) 分割で得られた2つの数列をまたぐ数列の中で、最も長い素数和を見つける (3) (1),(2)で得られた素数和のうち長い方を採用
(1),(2)を再帰的に繰り返し、十分小さな数列に対して探索してから、統合していく。
全く教科書通りの分割統治法である。
とか言うてますけど、実際は分割統治法を採用してもしなくても、ほとんど変わらない実行時間で終わる。一番下のsearchという関数がそれである。総当りと分割統治の差は20%程度。なので言うほどの工夫が必要なわけではなかったというのが真相である。
一応コメントしておくと、毎回毎回素数和を計算するのが邪魔くさいので、一番最初に（n,n番目までの素数の和）をタプルにしたリストを作成している（prmSets）。こうしておくと、連続する素数の両端を指定するだけで、その間の素数の和を求めることができる。これも工夫と言えば工夫である。
なんだかなあ☆
