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案 普通にSelect

「連続する素数」とあるので,各数の間の数はすべて合成数です。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 の項は合成数

これで解いたところ28秒でした。

第2案 NextPrime[]を使う

NextPrime[n] で「n より大きい最初の素数」,NextPrime[n, k] で「n より大きい k 番目の素数」を得ることができます。「n^2+13 の次の素数は n^2+27」で解くと27秒。第1案と同じと言ってよいと思います。

「n^2+1 の4つ先の素数は n^2+13,さらにその次は n^2+27」で解くと,約3倍の時間がかかります。途中の数を全部チェックしているせいでしょう。

第3案 共有変数を使う

正解者掲示板の解答例を参考にして共有変数を使ってみました。条件をみたす数を共有変数 a に格納していって,総和を求めます。時間は29秒でした。結局どの方法でも大差ありませんでした。