haskell - Haskell 中的质因数函数

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

-- 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)

上半部分不是我写的，效果很好。我试图让下半场工作，但事实并非如此。阅读代码中的注释以更好地理解我正在尝试做什么。谢谢!哦，请不要只是喷出答案。给我一些关于如何做的提示，也许有什么问题。

最佳答案

怎么了

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

一些提示

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

基本情况 没有递归调用，这会停止递归并返回结果的最后部分。

递归情况 在这里您修改函数的参数并使用修改后的参数再次调用它，也可能返回部分结果。

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

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

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

希望能帮到你，如果有任何问题，请不要犹豫，问。

关于haskell - Haskell 中的质因数函数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25880023/