- Prime-counting function
mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number"x" cite book |first=Eric |last=Bach |coauthors=Shallit, Jeffrey |year=1996 |title=Algorithmic Number Theory |publisher=MIT Press |id=ISBN 0-262-02405-5 |pages=volume 1 page 234 section 8.8] MathWorld |title=Prime Counting Function |urlname=PrimeCountingFunction] . It is denoted by (this does "not" refer to the number π).
Of great interest in
number theoryis the growth rateof the prime-counting function cite book | first=Leonard Eugene | last=Dickson | year=2005 | title=History of the Theory of Numbers I: Divisibility and Primality | publisher=Dover Publications | id=ISBN 0-486-44232-2] . It was conjectured in the end of the 18th century by Gauss and by Legendre to be approximately
in the sense that
This statement is the
prime number theorem. An equivalent statement is
where "li" is the
logarithmic integralfunction. This was first proved in 1896 by Jacques Hadamardand by Charles de la Vallée Poussin independently, using properties of the Riemann zeta functionintroduced by Riemann in 1859.
More precise estimates of are now known; for example
where the "O" is
big O notation. Proofs of the prime number theorem not using the zeta function or complex analysiswere found around 1948 by Atle Selbergand by Paul Erdős(for the most part independently) cite book | first=Kenneth | last=Ireland | coauthors=Rosen, Michael | year=1998 | title=A Classical Introduction to Modern Number Theory | edition=Second edition | publisher=Springer | id=ISBN 0-387-97329-X ] .
Another conjecture about the
growth ratefor prime series involving the prime number theorem is
Table of π("x"), "x" / ln "x", and li("x")
The table shows how the three functions π("x"), "x" / ln "x" and li("x") compare at powers of 10. See also cite web |title=Tables of values of pi(x) and of pi2(x) |url=http://www.ieeta.pt/~tos/primes.html |publisher=Tomás Oliveira e Silva |accessdate=2008-09-14] , cite web |title=Values of π(x) and Δ(x) for different x's |url=http://www.primefan.ru/stuff/primes/table.html |publisher=Andrey V. Kulsha |accessdate=2008-09-14] and cite web |title=A table of values of pi(x) |url=http://numbers.computation.free.fr/Constants/Primes/pixtable.html |publisher=Xavier Gourdon, Pascal Sebah, Patrick Demichel |accessdate=2008-09-14] .
The π("x") column is sequence [http://www.research.att.com/projects/OEIS?Anum=A006880 A006880] in OEIS; π("x") - "x" / ln "x" is sequence [http://www.research.att.com/projects/OEIS?Anum=A057835 A057835] ; and li("x") − π("x") is sequence [http://www.research.att.com/projects/OEIS?Anum=A057752 A057752] . The value for π(1023) is by T. O. e Silva .
Algorithms for evaluating π("x")
A simple way to find , if is not too large, is to use the
sieve of Eratosthenesto produce the primes less than or equal to and then to count them.
A more elaborate way of finding is due to Legendre: given , if , , …, are distinct prime numbers, then the number of integers less than or equal to which are divisible by no is
Wikimedia Foundation. 2010.
Look at other dictionaries:
Prime number — Prime redirects here. For other uses, see Prime (disambiguation). A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is… … Wikipedia
Prime number theorem — PNT redirects here. For other uses, see PNT (disambiguation). In number theory, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are… … Wikipedia
Prime gap — A prime gap is the difference between two successive prime numbers. The n th prime gap, denoted g n , is the difference between the ( n +1) th and the n th prime number, i.e.: g n = p n + 1 − p n .We have g 1 = 1, g 2 = g 3 = 2, and g 4 = 4. The… … Wikipedia
Prime factor — In number theory, the prime factors of a positive integer are the prime numbers that divide into that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization.For a … Wikipedia
Chebyshev function — The Chebyshev function ψ(x), with x < 50 The function ψ( … Wikipedia
Arithmetic function — In number theory, an arithmetic (or arithmetical) function is a real or complex valued function ƒ(n) defined on the set of natural numbers (i.e. positive integers) that expresses some arithmetical property of n.  An example of an arithmetic… … Wikipedia
Riemann zeta function — ζ(s) in the complex plane. The color of a point s encodes the value of ζ(s): dark colors denote values close to zero and hue encodes the value s argument. The white spot at s = 1 is the pole of the zeta function; the black spots on the… … Wikipedia
Von Mangoldt function — In mathematics, the von Mangoldt function is an arithmetic function named after German mathematician Hans von Mangoldt. Contents 1 Definition 2 Dirichlet series 3 Mellin transform … Wikipedia
Twin prime — A twin prime is a prime number that differs from another prime number by two. Except for the pair (2, 3), this is the smallest possible difference between two primes. Some examples of twin prime pairs are (3, 5), (5, 7), (11, 13), (17, 19), (29,… … Wikipedia
List of prime numbers — This is an incomplete list, which may never be able to satisfy particular standards for completeness. You can help by expanding it with reliably sourced entries. By Euclid s theorem, there are an infinite number of prime numbers. Subsets of the… … Wikipedia