PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 501 / 8個の約数

24の約数は8個である。
1, 2, 3, 4, 6, 8, 12, 24
ちょうど8個の約数を持つ n 以下の自然の個数を f(n) としよう。
f(100) = 10, f(1000) = 180, f(106) = 224427
f(10^12) を求めよ。

Problem 501 - Project Euler


8個の約数をもつ数は
p^3, p^3 q, pqr(p, q, r は相異なる素数)
のいずれかの形をしています。まともに計算すると p^3 q は二重ループ,pqr は三重ループになって膨大な時間がかかるので,そこをどう避けるかがこの問題のポイントです。

p^3 q の処理法がわかれば,pqr の処理法もわかりそうな気がします。

p を決めると,q の候補は n/p^3 以下の素数に限られます。その個数は
PrimePi[n/p^3]個。ただし,p は選べないので正確にはこうなります。

  • p^4 ≦ n のとき,PrimePi[n/p^3]-1 個
  • p^4 > n のとき,PrimePi[n/p^3] 個

pqr (p< q< r) も基本的には同じです。p,q を決めると,r の候補は
n/(pq) 以下の素数に限られます。ただし,q 以下の素数は選べません。

以上をもとにコードを書いた結果,11秒でした。