4 ms·
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
by majewsky 7y ago
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]
- bjoli 7y agoIt 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.
- ahakki 7y agothis? 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
- bjoli 7y agoThe lazy sieve i have seen, taken from the paper mentioned in my post: primes = sieve [2..] sieve (p : xs) = p : sieve [x | x <− xs, x ‘mod‘ p > 0]