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 -> x*x  Integer
firstPrimeDivisor x = head [p | p <- 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 -> xx xx

-
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 -> Integer -> [Integer]
factorize _ 1 = [] 
factorize d n 
    | d * d > n = [n]
    | n `mod` d == 0 = d : factorize d (n `div` d)
    | otherwise = factorize (d + 1) n

primeFactors :: Integer -> [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 > 1), where d is the smallest divisor of n. But then p

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

StackExchange Code Review Q#87954, answer score: 4