Haskell allows you to define the full list of prime numbers in just two lines:
module Primes where
primes = 2 : filter isPrime [3..]
isPrime x = all (\y -> mod x y /= 0) $ takeWhile (\y -> y * y < x) primes
The beauty of this is that it's self-referential. The list `primes` is built by filtering all the natural numbers for prime numbers, using the predicate `isPrime` which itself uses the list `primes`. The only caveat is that we need to encode that 0 and 1 are not prime numbers, but 2 is a prime number, to provide the base cases for the recursion. Furthermore, `isPrime` uses that each non-prime number has at least one prime factor less than or equal to its square root, to ensure that it only needs to look at a finite number of possible prime factors.
If you have GHC in your repo, you can test this by putting it in a file and running `ghci` with the file as the only argument. It will give you a REPL where `primes` and `isPrime` are in scope:
*Primes> isPrime 200
False
*Primes> take 10 primes
[2,3,5,7,11,13,17,19,23,29]
It is also dirt slow. This is just trial division, done in a lazy fashion.
At least it is better than the one some haskellers call the sieve of erathostenes (it isn't the sieve of erathostenes), which is so god-awful that I almost vomit every time I see it.
The real lazy sieve of erathostenes is a thing of wonder! There is a paper describing it called "the genuine sieve of erathostenes" and it can be found by googling.
sieve :: Integral a => a -> [a]
sieve l =
sieve' [2..l] []
where
sieve' (p:ns) ps =
sieve' (filter (\x -> rem x p /= 0) ns) (p : ps)
sieve' [] ps =
reverse ps
If you have GHC in your repo, you can test this by putting it in a file and running `ghci` with the file as the only argument. It will give you a REPL where `primes` and `isPrime` are in scope: