Euler项目haskell代码怎么这么快？

Question

我在ProjectEuler中处理401问题，我用python编写了我的解决方案，但运行起来需要几天时间，显然我需要加快速度或使用不同的方法。我在Haskell中遇到了一个解决方案，它看起来与我的python解决方案几乎完全相同，但几乎是在瞬间完成的。在

有人能解释一下为什么这么快吗？（我不是在寻求401问题的帮助或解决方案）

divisors n = filter (\x -> n `mod` x == 0) [1..(n`div`2)] ++ [n]
sigma2 n = sum $ map (\x -> x * x) (divisors n)
sigma2big n = sum $ map (sigma2)[1..n]
let s2b = sigma2big 10^15
putStrLn ("SIGMA2(10^15) mod 10^9 is " ++ (show (mod s2b 10^9)))

据我所知，它只是使用试算除法生成除数列表，将除数平方并求和，然后将结果从1到n相加

编辑：忘了我的python代码

^{pr2}$

Answer 1

请确保您使用Integer进行计算，而不是使用Int，因为10^15将使Int值溢出。在

如果您更改：

let s2b = sigma2big 10^15

收件人：

^{pr2}$

Haskell代码在ghci中耗尽了内存，我在运行编译版本时没有费心等待它完成。在

Answer 2

Prelude> sigma2big 1000
401382971
(0.48 secs, 28491864 bytes)

Prelude> sigma2big 10^3
103161709
(0.02 secs, 1035252 bytes)

Prelude> (sigma2big 10)^3
103161709

函数优先级（shh…）