Project Euler 146

滅茶苦茶汚いコードだし理論もクソだったのでコードは載せない.

 

考え方は10<= n <= 150000000まで回してその一つ一つにn^2+1, ..., n^2+27を計算しそれぞれをMR法で素数か判定する. この時全体の時間を考えるとMR法で生成する乱数は少ない方が良い. 3回もやれば概ね合っている.

n^2+1, ... , n^2+27 たちが素数になったn をリストに保存しておく. これが本当に素数になるか更に調査するために再びMR法にかける. このときは荒い素数判定で篩にかけたので候補が少ない, よってMR法の乱数生成を増やしてより正確に判定する.

最後に必要な条件はn^2+1, ... , n^2+27たちが連続した素数であるかということ.

これを調べるには1<=j <=27でj != 1,3,5,9,13,27でMR(n^2+j)を調べ素数になった場合, n^2+1, .. ,n^2+27の間に素数が存在しているということになり, 条件と異なる. よってこの場合のn をリストから外す.

最後にリストから和を取れば完成.

5分ほど時間がかかったが答えは出た.