arithmoi-0.6.0.1: Efficient basic number-theoretic functions.

Copyright (c) 2011 Daniel Fischer MIT Daniel Fischer Provisional Non-portable (GHC extensions) None 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 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.