Math.NumberTheory.Primes.Counting

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

Exact functions

primeCount :: Integer -> Integer

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.

primeCountMaxArg :: Integer

Maximal allowed argument of primeCount. Currently 8e18.

nthPrime :: Int -> Prime Integer

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.

Approximations

approxPrimeCount :: Integral a => a -> a

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

approxPrimeCountOverestimateLimit :: Integral a => a

Following property holds:

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

nthPrimeApprox :: Integer -> Integer

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

nthPrimeApproxUnderestimateLimit :: Integer

Following property holds:

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