求解方程 a * b = c，其中 a、b 和 c 为自然数

Question

我有一些自然数c。我想找到所有的自然数对a and b，其中a < b，例如a * b = c。

我有解决办法：

solve c = do solveHelper [1..c] c where
                   solveHelper xs c = do
                       x <- xs
                       (division, modulo ) <- return (c `divMod` x)
                       True <- return (modulo  == 0)
                       True <- return (x <= division)
                       return (x, division)

示例：

*Main> solve 10
[(1,10),(2,5)]

有没有办法加速我的代码，或者我应该使用更好的算法？

Answer 1

有一项优化您没有使用：您不必尝试从 0 到 c 的每个值。

a < b 和 a * b = c，所以 a * a < c，这意味着您只需要尝试从 0 到 sqrt c 的数字。或者，如果您不想计算 c 的平方根，您可以在 a * a >= c.

时立即停止

为此，您可以将 [1..c] 替换为 (takeWhile (\x -> x * x < c) [1..])。

Answer 2

你可以做得更好，更好。基本思想是这样的：首先，分解数字；然后枚举分解的分区。每个分区的产品是一个解决方案。那里有快速分解算法，但即使是最朴素的算法也会对您的代码进行相当大的改进；所以：

factorize :: Integer -> [Integer]
factorize n
    | n < 1 = error "no. =("
    | otherwise = go 2 n
    where
    go p n | p * p > n = [n]
    go p n = case quotRem n p of
        (q, 0) -> p:go p q
        _      -> go (p+1) n

我将使用非常好的 multiset-comb 包来计算因子集的分区。它不支持开箱即用的常用 Foldable/Traversable 内容，因此我们必须推出自己的 product 操作——但实际上这可能比使用标准界面无论如何都会给我们的product。

import Math.Combinatorics.Multiset

productMS :: Multiset Integer -> Integer
productMS (MS cs) = product [n^p | (n, p) <- cs]

divisors :: Integer -> [(Integer, Integer)]
divisors n =
    [ (a, b)
    | (aMS, bMS) <- splits (fromList (factorize n))
    , let a = productMS aMS; b = productMS bMS
    , a <= b
    ]

对于不公平的时间，我们可以在ghci中进行比较：

*Main> :set +s
*Main> length $ solve (product [1..10])
135
(3.55 secs, 2,884,836,952 bytes)
*Main> length $ divisors (product [1..10])
135
(0.00 secs, 4,612,104 bytes)
*Main> length $ solve (product [1..15])
^CInterrupted. [after several minutes, I gave up]
*Main> length $ divisors (product [1..15])
2016
(0.03 secs, 33,823,168 bytes)

这里 solve 是你的解决方案，divisors 是我的。为了公平比较，我们应该编译；我使用了这个程序：

main = print . last . solve . product $ [1..11]

（类似于 divisors 代替 solve。）我用 -O2 编译；你的总共用了 1.367 秒，我的总共用了 0.002 秒。

求解方程 a * b = c，其中 a、b 和 c 为自然数

Solve the equation a * b = c, where a, b and c are natural numbers

haskell

equation

brute-force