--/--/--

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

2008/10/12

Project Euler: Problem 12

Problem 12

約数の個数を簡単に求める公式なんてものがあるらしい。知らなかった。はじめはアドホックに約数の個数を求めていたのだけど、なんかありそうだよなーと思って調べてみたらあった。速度的にも結構改善された。数分かかってたのが10数秒くらいになるとか。

参考リンク:

実行結果

$ time runhaskell 12.hs
76576500

real 0m24.888s
user 0m24.830s
sys 0m0.020s

プログラム

 1 triNum n = sum $ take n [1..]
 2
 3 ------------------------------------------------------------
 4 primes = sieve [2..]
 5   where sieve (p:ps) = p : sieve [x | x <- ps, x `mod` p /= 0]
 6
 7 primeDivs n = f' n primes [] 0
 8   where f' n pps@(p:ps) r c
 9            | n < p          = (p,c):r
10            | n `mod` p == 0 = f' (n `div` p)  pps r (c+1)
11            | otherwise      = if c == 0
12                                 then f' n ps r 0
13                                 else f' n ps ((p,c):r) 0
14
15 divsCount = product . map ((+1. snd) . primeDivs
16
17 ------------------------------------------------------------
18 = (fst . head) $
19     dropWhile ((< 501. snd) $
20     map (\-> let t = triNum n in (t,divsCount t)) [1..]
21
22 main = print $ f
スポンサーサイト

comment

post




上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。