読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

Project Euler 146

PE

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

 

考え方は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分ほど時間がかかったが答えは出た.