約数の和の求め方色々。
リスト内包表記でワンライナー
divSum n = sum [m| m <- [1..n `div` 2], n `mod` m == 0]確かに約数を求めたければ、1からnまでではなく1から n`div`2 までで良かった。2で割り切れればそれが最大の約数なので。
約数関数を利用
約数関数の記事を読んだだけでは理解が追いつかなかったが、以下のコメントを参考にコードを書いてみて動作を確認しつつ解いてみた。
@so_zaneli 例えば 2^a * 3^b * 5^c の（その数自身を含む）約数の和は (2^(a+1) - 1)/(2-1) * (3^(b+1) - 1)/(3-1) * (5^(c+1) -1)/(5-1) と計算は簡単です。（素因数分解さえできてれば）
— [1..100]＞＞=pen (@1to100pen) 2013, 12月 4primeFactorsを使って素因数分解すると、以下の関数でその数自身を含む約数の和を求められる。divSum = product . map (\(b, e) -> (b ^ (e + 1) - 1) `div` (b - 1)) . primeFactorsその数自身を引けば真の約数を求められる。これを別関数
primeFactorsとした。実行時間は、元々のeuler21-1.hsが最も遅く3秒程度、euler21-2.hsが1～2秒程度、euler21-3.hsが最も速く1秒未満、となった。