## Sieve of Eratosthenes In Haskell

Algorithm description, see Sieve of Eratosthenes

module Main where import System.Environment isPrime p (x:xs) | x*x > p = True | p `mod` x == 0 = False | otherwise = isPrime p xs primes = 2 : oprimes where oprimes = 3 : [ p | p <- [5,7..], isPrime p oprimes] main = do args <- getArgs let n = read $ args !! 0 x = takeWhile (< n) primes print $ length x print x

There is a HackageDB package called primes which provides an efficient lazy wheel sieve for prime generation.

This version looks nicer, but less effective:

sieve (x:xs) = x : sieve xs' where xs' = filter (\y -> y `mod` x /= 0) xs primes = 2 : sieve [3,5..]

See also The Genuine Sieve of Eratosthenes

Advertisements

## Leave a Reply