整数n的除数列表（Haskell）

Question

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

-- 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是素数的平方时，如何找到避免重复的更好方法？

Answer 1

[要确定瓶颈在哪里，请在顶层放置三个辅助定义（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。

Answer 2

您不必测试all下半部分的元素。您知道如果存在平方根，则它是其中的head元素：

          secondHalf = let (r:ds) = [n `div` d | d <- reverse firstHalf]
                       in [r | n `div` r /= r] ++ ds

这假设n为正。

更简单地处理数字的平方数的一种简单方法是对其进行处理[[单独地：

divs n = 
  let 
    r = floor $ sqrt $ fromIntegral n 
    (a,b) = unzip $ (1,n) : [(d, q) | d<-[2..r-1], let (q,r)=quotRem n d, r==0]
  in
    if r*r==n
      then a ++ r : reverse b
      else a ++ reverse b

这样，我们免费获得下半年，作为上半年的一部分。 
但是这在您的应用程序中几乎不是瓶颈，因为算法本身效率低下。通常到generate the divisors from a number's prime factorization要快得多。通过试验除法进行质因数分解可以更快，因为我们找到了每个除数，从而减少了因数分解的次数，从而减少了尝试除数的数量（最大为[[reduced

数的平方根） ）。例如，在分解过程中尝试使用12348 = 2*2*3*3*7*7*7和7以上的任何因子，而在divs 12348中，将数字12348除以从2到110的所有数字：

factorize n = go n (2:[3,5..])    -- or:  (go n primes)  where
   where                          --  primes = 2 :
     go n ds@(d:t)                --   filter (null.tail.factorize) [3,5..]
        | d*d > n    = [n]
        | r == 0     =  d : go q ds
        | otherwise  =      go n t
            where  (q,r) = quotRem n d