Prime factors in Haskell

Question

I'm new to Haskell.

How to generate a list of lists which contains prime factors of next integers?

Currently, I only know how to generate prime numbers:

primes = map head $ iterate (\(x:xs) -> [y | y<-xs, y `mod` x /= 0 ]) [2..]

Answer 1

A simple approach to determine the prime factors of n is to

• search for the first divisor d in [2..n-1]
• if D exists: return d : primeFactors(div n d)
• otherwise return n (since n is prime)

Code:

prime_factors :: Int -> [Int]

prime_factors 1 = []
prime_factors n
  | factors == []  = [n]
  | otherwise = factors ++ prime_factors (n `div` (head factors))
  where factors = take 1 $ filter (\x -> (n `mod` x) == 0) [2 .. n-1]

This obviously could use a lot of optimization (search only from 2 to sqrt(N), cache the prime numbers found so far and compute the division only for these etc.)

UPDATE

A slightly modified version using case (as suggested by @user5402):

prime_factors n =
  case factors of
    [] -> [n]
    _  -> factors ++ prime_factors (n `div` (head factors))
  where factors = take 1 $ filter (\x -> (n `mod` x) == 0) [2 .. n-1]