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

Portability Non-portable (GHC extensions) Provisional Daniel Fischer

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.