# Difference between revisions of "Prime numbers"

From HaskellWiki

(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
```