haskell - Haskell 中的质因式分解函数

Question

我正在尝试创建一个函数，用我给它的列表(无限)来显示数字的素因数。这是我到目前为止所拥有的:

-- Here is a much more efficient (but harder to understand) version of primes.
-- Try "take 100 primes" as an example (or even more if you like)
primes = 2 : primesFrom3 where 
    primesFrom3 = sieve [3,5..] 9 primesFrom3
    sieve (x:xs) b ~ps@(p:q:_)
      | x < b     = x : sieve xs b ps
      | otherwise =     sieve [x | x <- xs, rem x p /= 0] (q^2) (tail ps)



-- Write a function that factors its first argument using the (infinite)
-- list of available factors given in its second argument
-- (using rem x p /= 0 to check divisibility)
primeFactsWith :: Integer -> [Integer] -> [Integer]
primeFactsWith n (p:ps) = if (rem n p /= 0) then
                                (primeFactsWith n ps)
                          else (primeFactsWith p ps)

上半部分不是我写的，效果很好。我试图让后半部分发挥作用，但事实并非如此。阅读代码中的注释以更好地理解我想要做什么。谢谢!哦，请不要只是说出答案。给我一些关于如何做以及可能出了什么问题的提示。

Answer 1

出了什么问题

问题是您在两个分支中都进行了递归调用，因此该函数永远不会停止。

一些提示

要构建递归列表生成函数，您需要两个分支或案例:

• 基本情况无递归调用，这会停止递归并返回结果的最后部分。
• 递归情况在这里，您修改函数的参数并使用修改后的参数再次调用它，可能还会返回结果的一部分。

您需要在递归分支处有两个子分支。如果您找到了质因数，则为一个；如果当前数字不是质因数，则为另一个。

这是一个骨架，需要填写<>中的部分括号。

primeFactsWith :: Integer -> [Integer] -> [Integer]
primeFactsWith n (p:ps) = if <halt condition> then
                            <final result>
                          else if (rem n p /= 0) then
                            <not a factor - recursive call 1>
                          else 
                            <found a factor - return it, 
                             and make recursive call 2>

• 如果您找到了质因数，则可以将该数字除以它，得到一个较小的数字，而无需该因数。为了执行整数除法，Haskell 提供了一个名为 div 的函数。 .

• 如果您达到数字 1，则您已生成所有质因数，您可以停止。质因数列表的最后部分(位于其所有因数之后)是一个空列表。

• 如果不再需要任何素数，您可以从无限列表中删除它，但请注意，一个数字可能在因子列表中多次包含素数。如果您想删除p你可以只使用 ps ，从模式；如果你想保留p您必须使用(p:ps) .

• cons 运算符 (:)可用于构建列表。您可以使用它返回结果列表中的一个数字，并使用递归调用来查找剩余的数字，例如

  x : foo y z

希望对您有所帮助，如果您有任何疑问，请随时询问。