Portability | Non-portable (GHC extensions) |
---|---|
Stability | Provisional |
Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |
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