PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 549 / 階乗の整除性

10 が m! を割り切る最小の m は m=5 である。

25 が m! を割り切る最小の m は m=10 である。

n が m! を割り切る最小の m を s(n) とする。s(10)=5, s(25)=10 である。

2 ≤ i ≤ n において Σs(i) を S(n) とする。S(100)=2012 である。

S(10^8) を求めよ。

Problem 549 - Project Euler


まずは与えられた例の吟味から。

  • 10=2*5 が m! を割り切る最小の m は m=5
  • 25=5^2 が m! を割り切る最小の m は m=10

「100! の末尾に0が何個並ぶか?」みたいなもので,n を素因数分解して p^k(p は素数)ごとに s を求め,その最大値をとればよいことがわかります。この方針でやってみたら240秒。


高速化するため,いくつかの素数についてははじめから最小値を与えてみました。

たとえば 5 なら 5, 10, 15, 20 を境に s が1ずつ増え,25=5^2 で 2 増えます。これは一般化できて,素数 p に対しては p^p が境になります。 p^p が 10^8 を超えない p に対してあらかじめ値を与えてみたら,20秒速くなって220秒になりました。

1分の壁は厚いです。10^8-1 個もの数を素因数分解しているのが原因なんでしょうね……