Portability | non-portable |
---|---|
Stability | Provisional |
Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |
Number of primes not exceeding n
, π(n)
, and n
-th prime; also fast, but
reasonably accurate approximations to these.
- primeCount :: Integer -> Integer
- nthPrime :: Integer -> Integer
- approxPrimeCount :: Integral a => a -> a
- nthPrimeApprox :: Integral a => a -> a
Exact functions
primeCount :: Integer -> IntegerSource
is the number of (positive) primes not exceeding primeCount
n == π(n)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,
simply counts the primes not exceeding primeCount
nn
,
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.
Approximations
approxPrimeCount :: Integral a => a -> aSource
gives (for approxPrimeCount
nn > 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 -> aSource
gives (for nthPrimeApprox
nn > 0
) an
approximation to the n-th prime. The approximation
is fairly good for n
large enough. Dual to
, this estimate should err
on the low side (and does for approxPrimeCount
n < 10^12
).