arithmoi-0.9.0.0: Efficient basic number-theoretic functions.

Copyright(c) 2011 Daniel Fischer
LicenseMIT
MaintainerDaniel Fischer <daniel.is.fischer@googlemail.com>
Safe HaskellNone
LanguageHaskell2010

Math.NumberTheory.Primes.Counting

Contents

Description

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

Synopsis

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 :: Integer -> 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, and must not exceed nthPrimeMaxArg.

nthPrimeMaxArg :: Integer Source #

Maximal allowed argument of nthPrime. Currently 1.5e17.

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