|Maintainer||Daniel Fischer <firstname.lastname@example.org>|
Number of primes not exceeding
n-th prime; also fast, but
reasonably accurate approximations to these.
is the number of (positive) primes not exceeding
primeCount n == π(n)
For efficiency, the calculations are done on 64-bit signed integers, therefore
8 * 10^18.
O(n^0.5) space, the time complexity is roughly
For small bounds,
simply counts the primes not exceeding
for bounds from
30000 on, Meissel's algorithm is used in the improved form due to
D.H. Lehmer, cf.
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.