haskell - 在 Haskell 中有效求除数

Question

尝试在 Haskell 中解决 Project Euler 的问题 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，它返回 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

你知道我可能做错了什么吗？谢谢!

Answer 1

另一个问题是你生成的三角数虽然是正确的，但效率非常低。例如，要计算第 11 个数字，您要对 [1..11] 求和，然后要计算第 12 个数字，您要对 [1..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..]