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

Copyright (c) 2011 Daniel Fischer MIT Daniel Fischer Provisional non-portable None Haskell98

Math.NumberTheory.Primes.Counting

Contents

Description

Number of primes not exceeding `n`, `π(n)`, and `n`-th prime; also fast, but reasonably accurate approximations to these.

Synopsis

# Exact functions

`primeCount n == π(n)` is the number of (positive) primes not exceeding `n`.

For efficiency, the calculations are done on 64-bit signed integers, therefore `n` must not exceed `8 * 10^18`.

Requires `O(n^0.5)` space, the time complexity is roughly `O(n^0.7)`. For small bounds, `primeCount n` simply counts the primes not exceeding `n`, for bounds from `30000` on, Meissel's algorithm is used in the improved form due to D.H. Lehmer, cf. http://en.wikipedia.org/wiki/Prime_counting_function#Algorithms_for_evaluating_.CF.80.28x.29.

`nthPrime n` calculates the `n`-th prime. Numbering of primes is `1`-based, so `nthPrime 1 == 2`.

Requires `O((n*log n)^0.5)` space, the time complexity is roughly `O((n*log n)^0.7`. The argument must be strictly positive, and must not exceed `1.5 * 10^17`.

# Approximations

approxPrimeCount :: Integral a => a -> a Source

`approxPrimeCount n` gives (for `n > 0`) an approximation of the number of primes not exceeding `n`. The approximation is fairly good for `n` large enough. The number of primes should be slightly overestimated (so it is suitable for allocation of storage) and is never underestimated for `n <= 10^12`.

nthPrimeApprox :: Integral a => a -> a Source

`nthPrimeApprox n` gives (for `n > 0`) an approximation to the n-th prime. The approximation is fairly good for `n` large enough. Dual to `approxPrimeCount`, this estimate should err on the low side (and does for `n < 10^12`).