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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 146 / 素数パターンの調べ上げ

n^2+1, n^2+3, n^2+7, n^2+9, n^2+13, n^2+27 が連続する素数になる最小の正整数 n は 10 である。100万未満の n の総和は 1242490 である。

1億5000万未満の n の総和を求めよ。

Problem 146 - Project Euler

第1案 素朴な brute force

「連続する素数」とあるので,途中の数はすべて合成数です。n^2+k に対して

  • k=1, 3, 7, 9, 13, 27 は素数
  • k=5, 11, 15, 17, 19, 21, 23, 25 は合成数

これを全部調べるのは時間がかかりすぎるので,候補のしぼりこみをおこないます。

  • 与えられた数はすべて奇数なので n は偶数。
  • n^2+9 と n^2+27を考えると n は3の倍数ではない。このとき n^2 ≡ 1 (mod 3) なので k=11, 17, 23 の項は3の倍数つまり合成数になる。チェックしなくてよい。
  • mod 5 で考えると n ≡ ±1 のとき n^2+9 ≡ 0となり,n ≡ ±2 のとき n^2+11 ≡ 0 となるので n は5の倍数でなくてはならない。このとき k=5, 15 の数は合成数になるのでチェックしなくてよい。

まとめると n は10の倍数で,調べなければならない条件は次のとおりです。

  • k=1, 3, 7, 9, 13, 27 は素数
  • k=19, 21 は合成数

これで解いたところ106秒かかりました。

第2案 NextPrime[]を使う

NextPrime[n] で「n より大きい最初の素数」,NextPrime[n, k] で「n より大きい k 番目の素数」を得ることができます。「n^2+13 の次の素数は n^2+27」で解くと101秒。ちょっと速くなりますが,誤差みたいなものですね。

「n^2+1 の4つ先の素数は n^2+13,さらにその次は n^2+27」で解くと515秒。チェック項目を減らしたはずが,かえって遅くなるという意外な結果でした。

第3案 並列化

正解者掲示板の解答例を参考にして並列化してみました。条件をみたす数を共有変数 a に格納していって,総和を求めています。2コアの非力なPCでも5秒で終了。20倍……