使用列表理解进行素数分解

Question

我想.在Haskell中仅使用列表推导方法和/或(函数组合运算符)找到给定数字的所有素因子.我特别想避免递归解决方案.

例如,pfactors 120必须产生[2,2,2,3,5]输出.

我试过了:

pfactors n = [p | p <- [2..n], n `mod` p == 0, [d | d <- [1..p], p `mod` d == 0] == [1,p]]

但是当我打电话时pfactors 120,结果[2,3,5]并非所有的主要因素.

Answer 1

这是我如何做到的:

pfactors :: Integer -> [Integer]
pfactors n = [ p
             | p <- [2..n]                                  -- Possible factors
             , [d | d <- [1..p], p `mod` d == 0] == [1,p]   -- Are prime 
             , _ <- [ p | i <- [1..n], n `mod` p^i == 0] ]  -- Divisible powers

它本质上就是你所拥有的解决方案,但不同之处在于它在末尾有一个额外的列表理解,其中包含与p因子一样多的元素n.

免责声明我真的不会在现实中这样做.

编辑我觉得上面写的很脏,所以作为参考,这更接近我写的东西:

pfactors' :: Int -> [Int]
pfactors' = unfoldr firstFactor
  where
    firstFactor n =
        listToMaybe [(f, n `div` f)
                    | f <- [2..n]
                    , n `mod` f == 0]

依赖关系: Data.List (unfoldr),Data.Maybe (listToMaybe)