I'm working on problem 401 in project euler, I coded up my solution in python but it's going to take a few days to run, obviously I'll need to speed it up or use a different approach. I came across a solution in Haskell that looks almost identical to my python solution but completes almost instantaneously.
我正在研究项目euler中的问题401,我在python中编写了我的解决方案,但它需要几天才能运行,显然我需要加快速度或使用不同的方法。我在Haskell中遇到了一个与我的python解决方案几乎完全相同的解决方案,但几乎是瞬间完成的。
Can someone explain how it is so fast? (I AM NOT ASKING FOR HELP OR SOLUTIONS TO PROBLEM 401)
有人可以解释它是如此之快吗? (我不是要求帮助或解决问题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)))
From my understanding it is just using trial division to generate a list of divisors, squaring and summing them, and then summing the results from 1 to n.
根据我的理解,它只是使用试验除法生成一个除数列表,对它们进行平方和求和,然后将结果从1加到n。
EDIT: forgot my python code
编辑:忘了我的python代码
from time import clock
def timer(function):
def wrapper(*args, **kwargs):
start = clock()
print(function(*args, **kwargs))
runtime = clock() - start
print("Runtime: %f seconds." % runtime)
return wrapper
@timer
def find_answer():
return big_sigma2(10**15) % 10**9
def get_divisors(n):
divs = set()
for i in range(1, int(sqrt(n)) + 1):
if n % i == 0:
divs.add(i)
divs.add(n // i)
return divs
def sigma2(n):
return sum(map(lambda x: x**2, get_divisors(n)))
def big_sigma2(n):
total = 0
for i in range(1, n + 1):
total += sigma2(i)
return total
if __name__ == "__main__":
find_answer()
2 个解决方案
#1
43
Prelude> sigma2big 1000
401382971
(0.48 secs, 28491864 bytes)
Prelude> sigma2big 10^3
103161709
(0.02 secs, 1035252 bytes)
Prelude> (sigma2big 10)^3
103161709
function precedence (shh...)
功能优先(嘘......)
#2
2
Make sure you are using Integer
for your calculations and not Int
since 10^15
will overflow an Int
value.
确保您使用Integer进行计算而不是Int,因为10 ^ 15将溢出Int值。
If you change:
如果你改变:
let s2b = sigma2big 10^15
to:
至:
let s2b = sigma2big (10^15 :: Integer)
the Haskell code runs out of memory in ghci
and I didn't bother to wait for it to complete when running the compiled version.
Haskell代码在ghci中耗尽了内存,在运行编译版本时我没有等待它完成。
#1
43
Prelude> sigma2big 1000
401382971
(0.48 secs, 28491864 bytes)
Prelude> sigma2big 10^3
103161709
(0.02 secs, 1035252 bytes)
Prelude> (sigma2big 10)^3
103161709
function precedence (shh...)
功能优先(嘘......)
#2
2
Make sure you are using Integer
for your calculations and not Int
since 10^15
will overflow an Int
value.
确保您使用Integer进行计算而不是Int,因为10 ^ 15将溢出Int值。
If you change:
如果你改变:
let s2b = sigma2big 10^15
to:
至:
let s2b = sigma2big (10^15 :: Integer)
the Haskell code runs out of memory in ghci
and I didn't bother to wait for it to complete when running the compiled version.
Haskell代码在ghci中耗尽了内存,在运行编译版本时我没有等待它完成。