使用列表理解的素因分解 [英] Prime factorization using list comprehension

问题描述

我想在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] ，并非所有的主要因素。

解决方案

以下是我的做法：

  pfactors :: Integer  - > [整数] 
 pfactors n = [p 
 | p < -  [2..n]  - 可能的因素
，[d | d < -  [1..p]，p`mod`d == 0] == [1，p]  - 是素数
，_<  -  [p | i < -  [1..n]，n`mod` p ^ i == 0]]  - 可分割的权力
  

它本质上就是您的解决方案，但不同之处在于，它在最后包含了一个额外的列表理解，其中包含与 p 因素一样多的元素， code> n 。

声明我真的不会这样做。 / p>

编辑我觉得上面写的脏，所以作为参考，这更接近我写的内容：

  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）

I want to find all prime factors of a given number using only list comprehension method and/or . (function composition operator) in Haskell. I specifically want to avoid a recursive solution.

For example, pfactors 120 must produce [2,2,2,3,5] output.

I tried:

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

But when I call pfactors 120, the result is [2,3,5], not all prime factors.

解决方案

Here's how I'd do it:

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

It's essentially the solution you have, but the difference is that it has an extra list comprehension at the end which contains as many elements as p factors into n.

Disclaimer I really wouldn't do it like this in reality.

EDIT I felt dirty writing the above, so for reference, this is something closer to what I would write:

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

Dependencies: Data.List (unfoldr), Data.Maybe (listToMaybe)

这篇关于使用列表理解的素因分解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！