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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 347 / 二つの素数で割り切れる最大の整数

素数2と3の両方のみで割り切れる最大の整数 ≤ 100 は96である。
96 = 2^5*3
2つの異なる素数 p と q に対し,p と q の両方のみで割り切れる最大の正の整数 ≤N を M(p,q,N) とする。そのような正の整数が存在しなければ M(p,q,N) = 0 である。

たとえば M(2,3,100) = 96 である。
M(3,5,100) = 75 であって 90 ではない。90 は 2, 3, 5 で割り切れるためである。
また,M(2,73,100) = 0 である。2 と 73 の両方で割り切れる正の整数 ≤ 100 は存在しないためである。

すべての M(p,q,N) の和を S(N) とする。S(100) = 2262 である。

S(10,000,000) を求めよ。

Problem 347 - Project Euler

まずは正攻法で

はじめは素直に考えました。1~10^n から i番目の素数 pi と j番目の素数 pj だけで割り切れる数の集合を抽出して,その最大値の和を求めるというものです。

抽出を「素数の個数」「pi, pj」の2段階に分けたり,i, j の候補を絞ったりしましたが,時間的にちょっと無理でした。10^n (n=2, 3, 4, 5)に対してそれぞれ
0.005秒,0.1秒,3秒,180秒かかります。この倍率だと n=7 は数日(以上?)かかりそうです。


素数でグループ分け

上のコードの f のような関数を使わない形にしたらうまくいきました。10^7 で47秒。10^5 の場合で比べると,180秒→0.7秒と約250倍速くなったことになります。

  1. PrimeNu で2つの素数で割り切れる数を抽出
  2. 素因数分解
  3. GatherBy で素数の組ごとにグループ分け
  4. 各グループの最大値の総和を求める