Prime numbers

From HaskellWiki
Revision as of 16:33, 5 February 2007 by MathematicalOrchid (talk | contribs) (I hope this amuses somebody...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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) = 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) $ takeWhile (n >) primes)

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

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