arithmoi-0.12.1.0: Efficient basic number-theoretic functions.

Copyright | (c) 2011 Daniel Fischer
License | MIT
Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com>
Safe Haskell | Safe-Inferred
Language | Haskell2010

Math.NumberTheory.Primes.Counting

Contents

- Exact functions
- Approximations

Description

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

Synopsis

- primeCount :: Integer -> Integer
- primeCountMaxArg :: Integer
- nthPrime :: Int -> Prime Integer
- approxPrimeCount :: Integral a => a -> a
- approxPrimeCountOverestimateLimit :: Integral a => a
- nthPrimeApprox :: Integer -> Integer
- nthPrimeApproxUnderestimateLimit :: Integer

# Exact functions

primeCount :: Integer -> Integer Source #

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

Maximal allowed argument of `primeCount`. Currently 8e18.

nthPrime :: Int -> Prime Integer Source #

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

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

Following property holds:

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

nthPrimeApprox :: Integer -> Integer Source #

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

nthPrimeApproxUnderestimateLimit :: Integer Source #

Following property holds:

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