有效地找到 Haskell 中的除数
Efficiently finding the number of divisors in Haskell
正在尝试解决 Haskell 中欧拉计划的问题 12。
The sequence of triangle numbers is generated by adding the natural
numbers.
So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five
hundred divisors?
我的解决方案适用于少量除数（例如给定 5，它 returns 28），但是当输入 500 时，它似乎会无限期地挂起。
-- Lazily generates infinite list of triangle numbers.
triangleNumbers :: [Integer]
triangleNumbers = map (\x -> sum [1..x]) [1..]
-- Given a number, returns the a tuple of how many divisors it has and the number.
numDivisors :: Integer -> (Int, Integer)
numDivisors num = (length [x | x <- [1..num], num `mod` x == 0], num)
p12 :: Integer
p12 = snd $ head $ filter (\x -> fst x > 500) $ map numDivisors triangleNumbers
你知道我可能做错了什么吗？谢谢！
问题是查找除数的函数非常慢，因为它要测试所有的数字。有更有效的功能。例如，在 Whosebug 上查看此问题的答案：Two simple codes to generate divisors of a number. Why is the recursive one faster?。
但是，如果您 Google 稍微了解一下，您会发现许多其他算法。
另一个问题是您生成的三角数虽然正确，但效率很低。例如，要计算要对 [1..11] 求和的第 11 个数字，然后计算要对 [1..12] 求和的第 12 个数字，它不使用先前计算的结果。
正如我在评论中提到的，您可以直接使用 n*(n+1)/2 计算第 n 个三角数。然而，即使您不知道这个公式，您也可以通过使用如下递归来利用连续三角数之间的相似性：
triangulars = go 1 2
where go s n = s : go (s+n) (n+1)
这种递归也被scanl函数捕获：
triangulars = scanl (+) 1 [2..]
正在尝试解决 Haskell 中欧拉计划的问题 12。
The sequence of triangle numbers is generated by adding the natural numbers.
So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...Let us list the factors of the first seven triangle numbers:
1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28 We can see that 28 is the first triangle number to have over five divisors.What is the value of the first triangle number to have over five hundred divisors?
我的解决方案适用于少量除数（例如给定 5，它 returns 28），但是当输入 500 时，它似乎会无限期地挂起。
-- Lazily generates infinite list of triangle numbers.
triangleNumbers :: [Integer]
triangleNumbers = map (\x -> sum [1..x]) [1..]
-- Given a number, returns the a tuple of how many divisors it has and the number.
numDivisors :: Integer -> (Int, Integer)
numDivisors num = (length [x | x <- [1..num], num `mod` x == 0], num)
p12 :: Integer
p12 = snd $ head $ filter (\x -> fst x > 500) $ map numDivisors triangleNumbers
你知道我可能做错了什么吗？谢谢！
问题是查找除数的函数非常慢，因为它要测试所有的数字。有更有效的功能。例如，在 Whosebug 上查看此问题的答案：Two simple codes to generate divisors of a number. Why is the recursive one faster?。
但是，如果您 Google 稍微了解一下，您会发现许多其他算法。
另一个问题是您生成的三角数虽然正确，但效率很低。例如，要计算要对 [1..11] 求和的第 11 个数字，然后计算要对 [1..12] 求和的第 12 个数字，它不使用先前计算的结果。
正如我在评论中提到的，您可以直接使用 n*(n+1)/2 计算第 n 个三角数。然而，即使您不知道这个公式，您也可以通过使用如下递归来利用连续三角数之间的相似性：
triangulars = go 1 2
where go s n = s : go (s+n) (n+1)
这种递归也被scanl函数捕获：
triangulars = scanl (+) 1 [2..]