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 |
Math.NumberTheory.Primes.Heap
Description
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, usemaxBound
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