有效地找到Haskell中的除数的数量

Question

试图解决Haskell的Euler项目中的问题12。

三角形数字的序列是通过将自然数加数字。

因此，第7个三角数将是1 + 2 + 3 + 4 + 5 + 6 + 7 =28。前十个项将是：

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

让我们列出前七个三角形的因子：

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.

第一个三角形数等于5的值是多少？100除数？

我的解决方案对于少数除数（例如，给定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..]

Answer 2

问题是查找除数数量的函数非常慢，因为它会测试所有数字。有更有效的功能。例如，在StackOverflow上查看此问题的答案：Two simple codes to generate divisors of a number. Why is the recursive one faster?。

但是如果您使用Google一点，您可能会找到许多其他算法。