Portability | portable |
---|---|

Stability | experimental |

Maintainer | leon@melding-monads.com |

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.

- primes :: Integral a => [a]
- sieve :: Integral a => a -> [a] -> [a]
- calcPrimes :: Integral a => () -> [a]
- primesToNth :: Integral a => Int -> [a]
- primesToLimit :: Integral a => a -> [a]

# Documentation

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

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]Source

An infinite stream of primes

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

Returns the first `n`

primes

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

Returns primes up to some limit