PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 50 / 連続する素数の和

素数41は6つの連続する素数の和として表せる。

41 = 2 + 3 + 5 + 7 + 11 + 13

100未満の素数を連続する素数の和で表したときにこれが最長になる。

同様に連続する素数の和で1000未満の素数を表したときに最長になるのは953で,21項を持つ。100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?

Problem 50 - Project Euler


我ながら地道に解いてしまった。

f, g, h はこういう関数です。

  • f[i,j]:i番目の素数からj番目の素数までの和
  • g[i]:i番目の素数からはじめた場合,「和が10^6未満」の条件で最大何番目の素数まで足せるか
  • h[i]:i番目の素数からはじめた場合,「和が素数」の条件で最大何番目の素数まで足せるか

100万以下のすべての素数について調べると,約1分かかります。ただ,後ろの方の素数からはじめた場合,あっという間に和が100万を越えてしまうのでそう何個も足せないはずです。そういう数についても調べるのは無駄なので,n の候補をしぼりこむことにしました。

最初の素数である2からはじめた場合,h[1]=536番目の素数まで足せるので g[n] - n >= h[1] - 1 をみたす n について調べれば十分です。その数 nmax=11 個。
100万以下の素数は PrimePi[10^6]=78498 個ですから,計算量を大幅に減らせます。

答えは4番目の素数7を先頭に542個の素数を足した997651です。