arithmoi-0.3.0.0: Efficient basic number-theoretic functions. Primes, powers, integer logarithms.

PortabilityNon-portable (GHC extensions)
StabilityProvisional
MaintainerDaniel Fischer <daniel.is.fischer@googlemail.com>
Safe HaskellSafe-Infered

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 Integer 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.

Synopsis

Documentation

primes :: Integral a => [a]Source

A list of primes. The sieve does not handle overflow, hence for bounded types, garbage occurs near maxBound. If primes that large are requested, use

   map fromInteger $ takeWhile (<= fromIntegral maxBound) primes

instead. Checking for overflow would be slower. The sieve is specialised for Int, Word and Integer, since these are the most commonly used. For the fixed-width 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 sieveFrom with different arguments.

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

sieveFrom n generates the list of primes >= n. The remarks about overflow and performance in the documentation of primes apply here too.