Difference between revisions of "Prime numbers"

From HaskellWiki
Jump to: navigation, search
(I hope this amuses somebody...)
 
(Corrected numerous outright bugs in the code (!))
Line 3: Line 3:
 
<haskell>
 
<haskell>
 
primes = sieve [2..] where
 
primes = sieve [2..] where
sieve (p:xs) = filter (\x -> x `mod` p == 0) xs
+
sieve (p:xs) = p : sieve (filter (\x -> x `mod` p > 0) xs)
 
</haskell>
 
</haskell>
   
Line 9: Line 9:
   
 
<haskell>
 
<haskell>
is_prime n = n `elem` (takeWhile (n >) primes)
+
is_prime n = n `elem` (takeWhile (n >=) primes)
   
factors n = filter (\p -> n `mod` p == 0) $ takeWhile (n >) primes)
+
factors n = filter (\p -> n `mod` p == 0) primes
   
 
factorise 1 = []
 
factorise 1 = []
Line 19: Line 19:
 
</haskell>
 
</haskell>
   
(Note the repeated use of <hask>takeWhile</hask> to prevent the infinite list of primes requiring an infinite amount of CPU time and RAM to process!)
+
(Note the use of <hask>takeWhile</hask> to prevent the infinite list of primes requiring an infinite amount of CPU time and RAM to process!)
   
 
[[Category:Code]]
 
[[Category:Code]]

Revision as of 10:13, 6 February 2007

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!)