Math.Sieve.ONeill

Incremental primality sieve based on priority queues, described in the paper The Genuine Sieve of Eratosthenes by Melissa O'Neill, Journal of Functional Programming, 19(1), pp95-106, Jan 2009.

http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Code is unchanged, other than packaging, from that written by Melissa O'Neill. This version contains optimizations not described in the paper, primarily improving memory consumption.

http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip

Documentation

primes :: Integral a => [a]

An infinite stream of primes

sieve :: Integral a => a -> [a] -> [a]

The first argument specifies which number to start at, the second argument is a wheel of deltas for skipping composites. For example, primes could be defined as

  2 : 3 : sieve 5 (cycle [2,4])

calcPrimes :: Integral a => () -> [a]

An infinite stream of primes

primesToNth :: Integral a => Int -> [a]

Returns the first n primes

primesToLimit :: Integral a => a -> [a]

Returns primes up to some limit