素数の計算はgmpで!?

gmpという巨人の肩があるので、素数系は「えいや」で片付ける目処がたっている。
ということで、目指すはProblem146

早速、実直に？実装してみた。
連続する素数というのがちょっと引っかかったけど、n**2+1が素数なら、
これに2を足して判断、以下、繰り返しで、リストを埋めていくというきわめて安直な実装をしてみた。
（計算中にgmpの関数を眺めていたらnext_primeなんて、そのまんまの関数があったのに気がついた）

n**2+1...のすべてが素数ならばリストに格納、前述のリストと合致すればOK
後はカウンタを積算していくだけ、と思っていたら、予定推定時間を過ぎてもなかなか終わらない
（計算がリニアな伸びをしていないんだろう。どこで遅くなっていたのかは？だけど）

しかたがないので、寝る前にぶん回しておいた。
ふと、夜中に目が覚めて、確認したところ、MemoryErrorになって止まっていた。
まぁ、多倍長整数をリストに突っ込んでいるんだから仕方がないといえなくもないけど、6*2で12ケ入れただけで？？
ってのはある。
（pythonはこの辺りは弱いっぽい）
他の言語で書き直すという選択肢は厳しい（笑）ので、n**2+1からの差分をとることにしてみた
（他にいい手を思いつかなかった）
これでメモリの消費量は激減するはず

後は時間をかけるだけ。今回は少しばかり枝刈り<*>1をしたのが良かったか、概ね予定通り（それでも約30分）で答えが出た<*>1（nが奇数の場合、n**2も奇数になる。これは今回の計算から除外できる。（n**2+1が偶数になるから））

ps
回答者だけが参照できるフォーラムを見ていたら、もっといい方法があるっぽい。（当たり前か）

>Java, 1.1 second on Core2duo@2.5GHz

文字通り、桁違いに速い

でも、このロジックがよく分からない（困）
（周期性があるので、分割してループを回すみたいなんだけど。
周期性はmoduloが鍵か。そこまではなんとなく分かる気はするのだけど。）

ブルートフォースに頼る辺り、まだまだ厳しいなぁ。
（というか、本来はこれは反則に近いのか？）
つまり、ほとんどの問題はエレガントな解決策があればカップラーメン時間で解けるんだろうなぁ。

まぁ、初めての3桁人問題ということでした（確認した時点で786人）