haskell - Haskell 有效地获得除数

Question

我想有效地找到整数 n 的正确除数。

我怎样才能做到这一点？

现在我正在使用以下功能

divisors :: (Integral a) => a -> [a]
divisors n = filter ((0 ==) . (n `mod`)) [1 .. (n `div` 2)]

但是我已经读过，当我只检查直到 n 的平方根的数字时，效率会更高。你有什么建议如何用平方根解决它吗？

标签： haskell

Answer 1

给定一个数n可以被k整除，那么n/k也是n的除数。事实上，因为n/(n/k)=k。如果k>√n，我们因此知道k/n<√n，因此，我们无需计算所有除数，而是每次找到一个除数时，也可以产生“co-divisor”。

因此，我们可以按如下方式实现算法：

divisors :: Integral a => a -> [a]
divisors n = concatMap f (filter ((==) 0 . mod n) (takeWhile (\k -> k*k <= n) [1 .. n]))
    where f k | k < l = [k, l]
              | otherwise = [k]
              where l = div n k

因此，在这里我们首先使用takeWhile (\k -> k*k <= n) [1 .. n]从1until 创建一个列表（如果它是整数则包括√n）。

接下来我们过滤这些元素，只保留那些除n. 最后，对于这些元素中的每一个，我们检查协除数是否不同。如果是这种情况，我们同时产生k和 co-divisor l，否则（这只会是这种情况√n），我们只产生k。

例如：

Prelude Data.List> divisors 1425
[1,1425,3,475,5,285,15,95,19,75,25,57]