Copyright | (c) 2011 Daniel Fischer |
---|---|

License | MIT |

Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |

Stability | Provisional |

Portability | non-portable |

Safe Haskell | None |

Language | Haskell2010 |

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 -> Integer Source

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

space, the time complexity is roughly *O*(n^0.5)

.
For small bounds, *O*(n^0.7)

simply counts the primes not exceeding `primeCount`

n`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.

# Approximations

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

gives (for `approxPrimeCount`

n`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 Source

gives (for `nthPrimeApprox`

n`n > 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`

).