Prime factorization using list comprehension

Question

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.

Tension

factors n = [p | p <- [2..n], n mod p == 0, [d | d <- [1..p], p mod d == 0] == [1,p]] – Tension

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

it has been already put. – Tension

Not what you have tried... – Halley

do you have a list of primes? – Amin

What you get is the list of unique prime factors of n, but as your example clearly shows, some factors occur more than once, and even if you did enumerate values several times, you wouldn't know how many times you have to do it to get all the multiple factors.. – Physician

Because the problem is unsolvable. – Physician

Yes didierc, that's right. Some factors occurs more than one time. But there must be a solution. How can I list all the multiple factors with list comprehension? – Tension

Yes, I don't understand neither @luqui – Tension

Probably because of the initial lack of code from the OP. – Gymnasiast

I think so, I am new here, so I did not notice. – Tension

Answer 1

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)

Styrax

Ok, I stand corrected, but shouldn't you filter to keep only the highest powers of each p? – Physician

Great @asQuirrel. That's my answer. Thank you very much! – Tension

@didierc, I don't believe so. What I'm doing here is keeping all the powers of p that divide n (by definition, these will be the smallest powers). – Styrax

Yeah, all the powers, but strictly speaking, shouldn't you only return the highest ones? (I say strictly, because one can always filter them afterwards, so your answer is ok). – Physician

I agree with you @asQuirrel. Recursive solution is the best one. But I was wondering whether it is possible with this method. Everything is possible with you:) Thanks. – Tension

@didierc, I'm still not following you, if you're talking about the value for p, it is checked for primality first, if you are talking about the last part (what I added), then the values are discarded, all we were actually interested in was the number of powers. – Styrax

Ahhh, ok, I did not understand your code. Very clever. – Physician

very nice listToMaybe trick!.. Though your formulation is inefficient; it should be factors n = unfoldr g (2,n) where g (d, n) = listToMaybe [(x, (x, div n x)) | n > 1, x <- [d..isqrt n]++[n], rem n x == 0]. More here. :) – Leitman

Very nice, that's the solution I was aiming for :) – Styrax

it's still suboptimal: it tests by all numbers instead of by primes only (precalculating the primes takes time but is worth it when doing more than a few calls to factors). cf. haskell.org/haskellwiki/… . But at least the deficiency is not quadratic... – Leitman