arithmoi- Efficient basic number-theoretic functions.

Copyright(c) 2011 Daniel Fischer
MaintainerDaniel Fischer <>
PortabilityNon-portable (GHC extensions)
Safe HaskellNone



Prime generation using a priority queue for the composites. The algorithm is basically the one described in, 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.



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.