Prime numbers: Difference between revisions
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 | 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 | factors n = filter (\p -> n `mod` p == 0) primes | ||
factorise 1 = [] | factorise 1 = [] | ||
| Line 19: | Line 19: | ||
</haskell> | </haskell> | ||
(Note the | (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!)