# Difference between revisions of "Prime numbers"

From HaskellWiki

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