Prime factorization in Haskell I am a Haskell beginner. Here is my function to find prime factors of a number

primes = 2:takePrimes [3, 5 ..]
    where takePrimes (x:xs) = let smallPrimes = untilRoot x primes
                              in  if 0 `notElem` (map (mod x) smallPrimes)
                                  then x:takePrimes xs
                                  else takePrimes xs

untilRoot n = takeWhile (\x -&gt; x*x &lt; n)

firstPrimeDivisor :: Integer -&gt; Integer
firstPrimeDivisor x = head [p | p &lt;- primes, x `mod` p == 0]

primeFactor 1 = []
primeFactor x = let p = firstPrimeDivisor x
                in p:primeFactor (x `div` p)


How does it look?
It looks fine, but there are a few issues with it:


When we check if a number is a prime, we need to test all possible divisors up its root inclusively. If you print the primes list, you'll see that 9 is there, which is obviously a bug. untilRoot n = takeWhile (\x -&gt; x*x &lt; n) should be untilRoot n = takeWhile (\x -&gt; x*x &lt;= n). However, this bug does not affect the correctness of your factorization algorithm.
It does not scale well. In the firstPrimeDivisor function, all primess up to x are checked in the worst case. That's why it works slowly even for moderately large prime numbers(for instance, 10^9 + 7).


Here a more efficient solution which checks only O(sqrt(n)) divisors in the worst case:

factorize :: Integer -&gt; Integer -&gt; [Integer]
factorize _ 1 = [] 
factorize d n 
    | d * d &gt; n = [n]
    | n `mod` d == 0 = d : factorize d (n `div` d)
    | otherwise = factorize (d + 1) n

primeFactors :: Integer -&gt; [Integer]
primeFactors = factorize 2


It is also much more concise. The idea behind it is to prove two statements first and then write a very simple code based on them:


The smallest divisor of any natural number greater than two is a prime. Let's assume that it is not the case and d = p * q (p, q &gt; 1), where d is the smallest divisor of n. But then p &lt; d and p is a divisor of n. Thus, d is not the smallest one. This statement also shows why your original solution is correct, even though the primes list is contains some composite numbers.
Any composite number has a divisor that does not exceed its square root. The proof by contradiction is very straightforward so I will omit it.