PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 249 / 素数の部分集合和

S={2, 3, 5, ..., 4999} を 5000 より小さい素数の集合とする。要素の合計が素数となるような S の部分集合の個数を求めよ。最下位の 16 桁を答えとして入力せよ。

Problem 249 - Project Euler


第250問(要素の合計が250で割り切れる部分集合の個数)とほとんど同じ方法で解けました。

variee.hatenadiary.com

Prime[k] まで使ったの部分集合の要素の合計の集合を A(k) であらわします。ここに Prime[k+1] を加えると3種類の部分集合ができます。

  • Prime[k+1] 単体
  • A(k) そのもの
  • A(k) の各元に Prime[k+1] を加えたもの

これらの個数をリストのシフトと足し算で求めます。14秒でできました。

かなり大きい数になるので,素数を増やすたびに mod 10^16 をとっています。こうしないと240秒かかります。