The prime-counting function, denoted by , is the number of prime numbers less than or equal to a real number . Thus
where denotes the number of elements in a finite set. For example, , because the primes not exceeding are and . It is a central object in number theory: its exact values describe the distribution of primes, while its approximations and error terms connect prime numbers with mathematical analysis and the Riemann zeta function.
Definition and elementary properties
The definition applies to all real , with for . Since primes are integers,
The function is nondecreasing and right-continuous. It is constant between consecutive primes and has a jump of size at every prime.
Using an indicator function, it can be written as
where equals when is prime and otherwise. In particular, for every integer ,
Some exact values are:
The symbol here is conventional and does not represent the circle constant.
Asymptotic distribution
The prime number theorem
The fundamental approximation is the prime number theorem:
where is the natural logarithm. The notation means that
This is a statement about relative error, not exact equality or a bounded absolute difference. The approximation becomes proportionally more accurate as grows, even though its absolute error need not become smaller.
One consequence is
Thus primes have natural density zero among the positive integers, despite being infinite in number.
The theorem also motivates the heuristic that an integer near a large value has a chance of approximately of being prime. This is an approximation to local density, not a claim that primality behaves as a sequence of independent random events. Divisibility and congruence restrictions impose strong arithmetic structure.
The logarithmic integral
A generally more accurate approximation is the logarithmic integral
Here denotes the Cauchy principal value, needed because the integrand is singular at . Another common convention uses
These functions differ by a constant.
Repeated integration by parts yields the asymptotic expansion
This is an asymptotic series, not a convergent expansion for a fixed finite . Keeping a fixed number of terms gives increasingly refined asymptotic descriptions as tends to infinity.
The prime number theorem is equivalently expressed as
Error terms and the Riemann hypothesis
The difference
measures the discrepancy between the exact count and its principal smooth approximation.
A classical unconditional estimate states that, for some constant ,
The Big O notation specifies an eventual bound up to a constant factor. Stronger unconditional estimates are known, but this form already improves substantially on the basic prime number theorem.
The Riemann hypothesis is equivalent to the estimate
This connects an assertion about zeros of a complex-valued function with a quantitative bound on the irregularity of prime distribution.
Although exceeds throughout very large computed ranges, it is not an upper bound for all . Littlewood proved in 1914 that
changes sign infinitely often. Agreement over a large finite range therefore does not establish a global inequality.
Weighted counting functions and zeta zeros
In analytic number theory, weighted prime counts are often easier to study than directly. The two Chebyshev functions are
and
where runs over primes and over positive integers. The second function counts prime powers, assigning the weight to each power of .
The prime number theorem is equivalent to either of the statements
Summation by parts gives the exact relation
Another useful function is Riemann’s weighted prime-power count:
It satisfies
For fixed , only finitely many terms are nonzero. Using the Möbius function , this relation can be inverted:
Riemann’s explicit formula expresses a version of in terms of the logarithmic integral, contributions from the nontrivial zeros of the zeta function, and additional correction terms. The zero contributions explain oscillations around the smooth approximation. At prime powers, an exact explicit formula requires an endpoint convention, commonly assigning the midpoint of a jump.
These identities provide a bridge between prime counting and complex analysis; their numerical use requires careful truncation and error control.
Exact computation
Sieving
The most direct systematic method is the sieve of Eratosthenes. It marks composite integers up to a chosen bound and counts the unmarked integers greater than .
A standard implementation uses elementary marking operations and storage proportional to . A segmented sieve processes successive intervals, reducing memory requirements while retaining primes up to for marking composites.
Sieving is particularly useful when the primes themselves are also needed. If only their number is required, more specialized algorithms can avoid enumerating every prime up to .
Legendre’s formula
Let be the primes in increasing order, and let count positive integers not exceeding that are divisible by none of the first primes. This auxiliary function is not Euler’s totient function.
It obeys the recurrence
If , then
The identity follows because every composite integer at most has a prime divisor at most . After multiples of those primes are removed, the survivors are and the primes greater than .
Meissel–Lehmer methods and later combinatorial algorithms refine this approach by organizing the remaining integers according to their prime factors. Analytic algorithms instead exploit zeta-function identities and controlled approximations. Both approaches can compute exact counts without producing a complete list of the primes being counted.
Historical development
Tables of primes helped reveal that their frequency decreases approximately according to a logarithmic law. In the late eighteenth and early nineteenth centuries, Carl Friedrich Gauss and Adrien-Marie Legendre developed influential approximations to the prime-counting function. Gauss associated prime density with , leading to the logarithmic-integral approximation; Legendre proposed approximations of the form .
In the mid-nineteenth century, Pafnuty Chebyshev established bounds showing that has the same order of magnitude as , without proving that their ratio tends to .
In 1859, Bernhard Riemann connected prime counting with the analytic properties of the zeta function. Jacques Hadamard and Charles Jean de la Vallée Poussin independently proved the prime number theorem in 1896 by showing, in particular, that the zeta function has no zeros on the line .
In 1949, Atle Selberg and Paul Erdős gave elementary proofs of the prime number theorem. Here “elementary” means that the proofs avoid complex-analytic methods, not that they are simple.
Related counting problems and limitations
If denotes the -th prime, then
The prime number theorem consequently implies
Counts in intervals are expressed by
the number of primes in . The prime number theorem alone does not justify replacing this expression by for every choice of a short interval length . Subtracting two global approximations may leave errors larger than the interval count itself.
A further extension counts primes in residue classes:
For fixed positive , when and are coprime, the prime number theorem for arithmetic progressions states
where is Euler’s totient function. Statements in which grows with require additional qualifications and stronger estimates.
Global prime counts therefore describe average distribution, but do not by themselves determine individual prime gaps, prime patterns, or distribution in very short intervals.