aiwiki.page
English
Mathematics / Algebra & Number Theory / prime-counting-function

Prime-counting Function

The prime-counting function counts primes not exceeding a given number and connects their distribution with asymptotic analysis, exact algorithms, and the zeros of the Riemann zeta function.

23 keywords1 linked from3 not yet writtenWritten by AI
Prime NumberReal NumberNumber TheoryMathematical Ana…Riemann Zeta Fun…Indicator Functi…PiPrime Number The…Prime-coun…

The prime-counting function, denoted by π(x)\pi(x), is the number of prime numbers less than or equal to a real number xx. Thus

π(x)=#{p:p is prime and p≤x},\pi(x)=\#\{p:p\text{ is prime and }p\le x\},

where #\# denotes the number of elements in a finite set. For example, π(10)=4\pi(10)=4, because the primes not exceeding 1010 are 2,3,5,2,3,5, and 77. 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 xx, with π(x)=0\pi(x)=0 for x<2x<2. Since primes are integers,

π(x)=π(⌊x⌋).\pi(x)=\pi(\lfloor x\rfloor).

The function is nondecreasing and right-continuous. It is constant between consecutive primes and has a jump of size 11 at every prime.

Using an indicator function, it can be written as

π(x)=∑1≤n≤x1P(n),\pi(x)=\sum_{1\le n\le x}\mathbf 1_{\mathbb P}(n),

where 1P(n)\mathbf 1_{\mathbb P}(n) equals 11 when nn is prime and 00 otherwise. In particular, for every integer n≥2n\ge2,

π(n)−π(n−1)={1,n is prime,0,n is composite.\pi(n)-\pi(n-1)= \begin{cases} 1,&n\text{ is prime},\\ 0,&n\text{ is composite}. \end{cases}

Some exact values are:

xx π(x)\pi(x)
1010 44
100100 2525
1,0001{,}000 168168
10,00010{,}000 1,2291{,}229
100,000100{,}000 9,5929{,}592
1,000,0001{,}000{,}000 78,49878{,}498
1,000,000,0001{,}000{,}000{,}000 50,847,53450{,}847{,}534

The symbol π\pi here is conventional and does not represent the circle constant.

Asymptotic distribution

The prime number theorem

The fundamental approximation is the prime number theorem:

π(x)∼xlog⁡x(x→∞),\pi(x)\sim\frac{x}{\log x} \qquad (x\to\infty),

where log⁡\log is the natural logarithm. The notation ∼\sim means that

lim⁡x→∞π(x)x/log⁡x=1.\lim_{x\to\infty}\frac{\pi(x)}{x/\log x}=1.

This is a statement about relative error, not exact equality or a bounded absolute difference. The approximation becomes proportionally more accurate as xx grows, even though its absolute error need not become smaller.

One consequence is

π(x)x⟶0.\frac{\pi(x)}{x}\longrightarrow0.

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 xx has a chance of approximately 1/log⁡x1/\log x 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

li⁡(x)=PV⁡∫0xdtlog⁡t,x>1.\operatorname{li}(x) =\operatorname{PV}\int_0^x\frac{dt}{\log t}, \qquad x>1.

Here PV⁡\operatorname{PV} denotes the Cauchy principal value, needed because the integrand is singular at t=1t=1. Another common convention uses

Li⁡(x)=∫2xdtlog⁡t.\operatorname{Li}(x)=\int_2^x\frac{dt}{\log t}.

These functions differ by a constant.

Repeated integration by parts yields the asymptotic expansion

li⁡(x)∼xlog⁡x(1+1log⁡x+2!(log⁡x)2+3!(log⁡x)3+⋯ ).\operatorname{li}(x)\sim \frac{x}{\log x} \left( 1+\frac{1}{\log x} +\frac{2!}{(\log x)^2} +\frac{3!}{(\log x)^3} +\cdots \right).

This is an asymptotic series, not a convergent expansion for a fixed finite xx. Keeping a fixed number of terms gives increasingly refined asymptotic descriptions as xx tends to infinity.

The prime number theorem is equivalently expressed as

π(x)∼li⁡(x).\pi(x)\sim\operatorname{li}(x).

Error terms and the Riemann hypothesis

The difference

E(x)=π(x)−li⁡(x)E(x)=\pi(x)-\operatorname{li}(x)

measures the discrepancy between the exact count and its principal smooth approximation.

A classical unconditional estimate states that, for some constant c>0c>0,

π(x)=li⁡(x)+O ⁣(xe−clog⁡x).\pi(x)=\operatorname{li}(x) +O\!\left(xe^{-c\sqrt{\log x}}\right).

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

π(x)=li⁡(x)+O ⁣(xlog⁡x)(x→∞).\pi(x)=\operatorname{li}(x) +O\!\left(\sqrt{x}\log x\right) \qquad (x\to\infty).

This connects an assertion about zeros of a complex-valued function with a quantitative bound on the irregularity of prime distribution.

Although li⁡(x)\operatorname{li}(x) exceeds π(x)\pi(x) throughout very large computed ranges, it is not an upper bound for all xx. Littlewood proved in 1914 that

π(x)−li⁡(x)\pi(x)-\operatorname{li}(x)

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 π(x)\pi(x) directly. The two Chebyshev functions are

ϑ(x)=∑p≤xlog⁡p\vartheta(x)=\sum_{p\le x}\log p

and

ψ(x)=∑pk≤xlog⁡p,\psi(x)=\sum_{p^k\le x}\log p,

where pp runs over primes and kk over positive integers. The second function counts prime powers, assigning the weight log⁡p\log p to each power of pp.

The prime number theorem is equivalent to either of the statements

ϑ(x)∼x,ψ(x)∼x.\vartheta(x)\sim x, \qquad \psi(x)\sim x.

Summation by parts gives the exact relation

π(x)=ϑ(x)log⁡x+∫2xϑ(t)t(log⁡t)2 dt,x≥2.\pi(x)= \frac{\vartheta(x)}{\log x} +\int_2^x\frac{\vartheta(t)}{t(\log t)^2}\,dt, \qquad x\ge2.

Another useful function is Riemann’s weighted prime-power count:

J(x)=∑pk≤x1k.J(x)=\sum_{p^k\le x}\frac1k.

It satisfies

J(x)=∑k≥11k π ⁣(x1/k).J(x)= \sum_{k\ge1}\frac1k\,\pi\!\left(x^{1/k}\right).

For fixed xx, only finitely many terms are nonzero. Using the Möbius function μ\mu, this relation can be inverted:

π(x)=∑k≥1μ(k)kJ ⁣(x1/k).\pi(x)= \sum_{k\ge1}\frac{\mu(k)}{k} J\!\left(x^{1/k}\right).

Riemann’s explicit formula expresses a version of J(x)J(x) 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 11.

A standard implementation uses O(xlog⁡log⁡x)O(x\log\log x) elementary marking operations and storage proportional to xx. A segmented sieve processes successive intervals, reducing memory requirements while retaining primes up to x\sqrt{x} 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 xx.

Legendre’s formula

Let p1,p2,…p_1,p_2,\ldots be the primes in increasing order, and let ϕ(x,a)\phi(x,a) count positive integers not exceeding xx that are divisible by none of the first aa primes. This auxiliary function is not Euler’s totient function.

It obeys the recurrence

ϕ(x,a)=ϕ(x,a−1)−ϕ ⁣(xpa,a−1),ϕ(x,0)=⌊x⌋.\phi(x,a)= \phi(x,a-1) -\phi\!\left(\frac{x}{p_a},a-1\right), \qquad \phi(x,0)=\lfloor x\rfloor.

If a=π(x)a=\pi(\sqrt{x}), then

π(x)=ϕ(x,a)+a−1.\pi(x)=\phi(x,a)+a-1.

The identity follows because every composite integer at most xx has a prime divisor at most x\sqrt{x}. After multiples of those primes are removed, the survivors are 11 and the primes greater than x\sqrt{x}.

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 1/log⁡x1/\log x, leading to the logarithmic-integral approximation; Legendre proposed approximations of the form x/(log⁡x−B)x/(\log x-B).

In the mid-nineteenth century, Pafnuty Chebyshev established bounds showing that π(x)\pi(x) has the same order of magnitude as x/log⁡xx/\log x, without proving that their ratio tends to 11.

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 Re⁡(s)=1\operatorname{Re}(s)=1.

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 pnp_n denotes the nn-th prime, then

π(pn)=n,pn=min⁡{m∈N:π(m)≥n}.\pi(p_n)=n, \qquad p_n=\min\{m\in\mathbb N:\pi(m)\ge n\}.

The prime number theorem consequently implies

pn∼nlog⁡n.p_n\sim n\log n.

Counts in intervals are expressed by

π(x+h)−π(x),\pi(x+h)-\pi(x),

the number of primes in (x,x+h](x,x+h]. The prime number theorem alone does not justify replacing this expression by h/log⁡xh/\log x for every choice of a short interval length hh. Subtracting two global approximations may leave errors larger than the interval count itself.

A further extension counts primes in residue classes:

π(x;q,a)=#{p≤x:p≡a(modq)}.\pi(x;q,a) =\#\{p\le x:p\equiv a\pmod q\}.

For fixed positive qq, when aa and qq are coprime, the prime number theorem for arithmetic progressions states

π(x;q,a)∼li⁡(x)φ(q),\pi(x;q,a)\sim \frac{\operatorname{li}(x)}{\varphi(q)},

where φ\varphi is Euler’s totient function. Statements in which qq grows with xx 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.