CODEWITHSUNDEEP
haskellprime-factoring
sasas
sasas

Reputation: 65

Prime factorization using list comprehension

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.

Upvotes: 3

Views: 1486

Answers (1)

amnn
amnn

Reputation: 3716

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)

Upvotes: 5

Related Questions