haskellprimesfactorizationprime-factoring

Prime factors in Haskell


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..]

Solution

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

    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]