Copyright | (c) 2011 Daniel Fischer |
---|---|

License | MIT |

Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |

Stability | Provisional |

Portability | Non-portable (GHC extensions) |

Safe Haskell | None |

Language | Haskell2010 |

Prime generation using a priority queue for the composites.
The algorithm is basically the one described in
http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf, but
it uses a more efficient heap for the priority queue and a
larger wheel, thus it is faster (in particular, the speed
penalty for

is much smaller) and uses less memory.
It is nevertheless very slow compared to a bit sieve.
This module is mainly intended for comparison and verification.`Integer`

# Documentation

primes :: Integral a => [a] Source

A list of primes. The sieve does not handle overflow, hence for
bounded types, garbage occurs near

. If primes that
large are requested, use`maxBound`

`map`

`fromInteger`

$`takeWhile`

(<=`fromIntegral`

`maxBound`

)`primes`

instead. Checking for overflow would be slower. The sieve is specialised
for

, `Int`

and `Word`

, since these are the most commonly
used. For the fixed-width `Integer`

`Int`

or `Word`

types, sieving at one of the
specialised types and converting is faster.
To ensure sharing of the list of primes, bind it to a monomorphic variable,
to make sure that it is not shared, use

with different
arguments.`sieveFrom`