Prime numbers

The following is an elegant (and highly inefficient) way to generate a list of all the prime numbers in the universe:

  primes = sieve [2..] where
    sieve (p:xs) = p : sieve (filter (\x -> x `mod` p > 0) xs)

With this definition made, a few other useful (??) functions can be added:

  is_prime n = n `elem` (takeWhile (n >=) primes)

  factors n = filter (\p -> n `mod` p == 0) primes

  factorise 1 = []
  factorise n =
    let f = head $ factors n
    in  f : factorise (n `div` f)

(Note the use of takeWhile to prevent the infinite list of primes requiring an infinite amount of CPU time and RAM to process!)

The following is a more efficient version of the same sieve:

  primes :: [Int]
  primes = 2 : (filter h [3,5..]) where
    f n p = rem n p /= 0
    g n p = p <= (floor $ sqrt ((fromIntegral n) :: Double))
    h n   = all (f n) $ takeWhile (g n) primes

Be sure to compile with optimization on, so the partial application (g n) isn't recomputed for each use.