Difference between revisions of "Prime numbers"

From HaskellWiki
Jump to: navigation, search
(Corrected numerous outright bugs in the code (!))
(Added efficient version of prime sieve)
Line 20: Line 20:
   
 
(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!)
 
(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!)
  +
  +
The following is a more efficient version of the same sieve:
  +
  +
<haskell>
  +
primes :: [Int]
  +
primes = 2 : (filter h [3,5..]) where
  +
f n p = rem n p /= 0
  +
g n = floor $ sqrt ((fromIntegral n) :: Double)
  +
h n = all (f n) $ takeWhile (<= (g n)) primes
  +
</haskell>
  +
   
 
[[Category:Code]]
 
[[Category:Code]]

Revision as of 07:50, 5 July 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!)

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   = floor $ sqrt ((fromIntegral n) :: Double)
    h n   = all (f n) $ takeWhile (<= (g n)) primes