performance - 整数n(Haskell)的除数的列表

我目前有以下函数来获取整数的除数：

-- All divisors of a number
divisors :: Integer -> [Integer]
divisors 1 = [1]
divisors n = firstHalf ++ secondHalf
    where firstHalf = filter (divides n) (candidates n)
          secondHalf = filter (\d -> n `div` d /= d) (map (n `div`) (reverse firstHalf))
          candidates n = takeWhile (\d -> d * d <= n) [1..n]

我最终将filter添加到secondHalf，因为当n是质数的平方时，除数重复出现。这似乎是解决此问题的非常低效的方法。

因此，我有两个问题：如何测量算法中是否确实存在瓶颈？如果是的话，当n是素数的平方时，如何找到避免重复的更好方法？

最佳答案

为了确定瓶颈在哪里，请在顶层放置三个辅助定义（firstHalf，secondHalf，候选），然后使用探查器在以下代码上运行代码：ghc -prof --make divisors.hs ./divisors 100 +RTS -p -RTS

另外，您知道最大的候选对象是sqrt n，因此不必考虑进行许多乘法d*d，只需考虑[1..floor (sqrt n)]

对于更好的算法，您应该读一本数学书，因为它不是与haskell相关的问题……您可以考虑的事情：如果“ a除以b”，那么对于a的所有除数d，d也除以b。
您将要使用记忆或动态编程来避免多次检查给定的d除b（例如，如果15和27除b，那么您只需对3个除b进行一次数学检查。只需看看您的b）除数表中是否有3。