求解方程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

你可以做得更好,更好.基本思路是这样的:首先,将数字分解; 然后枚举分解的分区.每个分区的产品都是一个解决方案.有快速的分解算法,但即使是天真的算法也是对你的代码的改进; 所以:

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.367s,总计0.002s.