arithmoi-0.9.0.0: Efficient basic number-theoretic functions.

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 primeCountMaxArg.

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.

Maximal allowed argument of primeCount. Currently 8e18.

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 nthPrimeMaxArg.

Maximal allowed argument of nthPrime. Currently 1.5e17.

# Approximations

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

approxPrimeCount n gives an approximation of the number of primes not exceeding n. The approximation is fairly good for n large enough.

Following property holds:

approxPrimeCount n >= primeCount n || n >= approxPrimeCountOverestimateLimit

nthPrimeApprox n gives an approximation to the n-th prime. The approximation is fairly good for n large enough.

Following property holds:

nthPrimeApprox n <= nthPrime n || n >= nthPrimeApproxUnderestimateLimit