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 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 :: Integer -> 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, and must not exceed 1.5 * 10^17.

Approximations

approxPrimeCount :: Integral a => a -> a

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

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