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

Portability Non-portable (GHC extensions) Provisional Daniel Fischer

Math.NumberTheory.Primes.Sieve

Description

Prime generation using a sieve. Currently, an enhanced sieve of Eratosthenes is used, switching to an Atkin sieve is planned (if I get around to implementing it and it's not slower).

The sieve used is segmented, with a chunk size chosen to give good (enough) cache locality while still getting something substantial done per chunk. However, that means we must store data for primes up to the square root of where sieving is done, thus sieving primes up to `n` requires `O(sqrt n/log n)` space.

Synopsis

Documentation

primes :: [Integer]Source

List of primes. Since the sieve uses unboxed arrays, overflow occurs at some point, but not before `10^6*fromIntegral (maxBound :: Int)` (I forgot where exactly).

`sieveFrom n` creates the list of primes not less than `n`.

data PrimeSieve Source

Compact store of primality flags.

Sieve primes up to (and including) a bound. For small enough bounds, this is more efficient than using the segmented sieve.

Since arrays are `Int`-indexed, overflow occurs when the sieve size comes near `maxBound :: Int`, that corresponds to an upper bound near `15/8*maxBound`. On `32`-bit systems, that is often within memory limits, so don't give bounds larger than `8*10^9` there.

List of primes in the form of a list of `PrimeSieve`s, more compact than `primes`, thus it may be better to use `psieveList >>= primeList` than keeping the list of primes alive during the entire run.

`psieveFrom n` creates the list of `PrimeSieve`s starting roughly at `n`. Due to the organisation of the sieve, the list may contain a few primes less than `n`. This form uses less memory than `[Integer]`, hence it may be preferable to use this if it is to be reused.

Generate a list of primes for consumption from a `PrimeSieve`.