Prime Number Theorem — Definition, Formula & Examples

The Prime Number Theorem states that the number of primes less than or equal to a large number

x

is approximately

\frac{x}{\ln x}

. In other words, primes thin out gradually, and this formula captures their average density with increasing accuracy as

x

grows.

Let $\pi(x)$ denote the prime-counting function, which gives the number of primes $p \leq x$ . The Prime Number Theorem asserts that $\pi(x) \sim \frac{x}{\ln x}$ , meaning $\lim_{x \to \infty} \frac{\pi(x)}{x / \ln x} = 1$ . Independently proved by Hadamard and de la Vallée-Poussin in 1896, the theorem relies on properties of the Riemann zeta function.

Key Formula

\pi(x) \sim \frac{x}{\ln x}

Where:

$\pi(x)$ = The number of prime numbers less than or equal to x
$x$ = A positive real number
$\ln x$ = The natural logarithm of x
$\sim$ = Asymptotic equivalence: the ratio of the two sides tends to 1 as x → ∞

How It Works

The theorem does not tell you exactly how many primes exist below

x

; it provides an asymptotic estimate. As

x

increases, the ratio of the true count

\pi(x)

to the approximation

\frac{x}{\ln x}

approaches 1. A sharper approximation uses the logarithmic integral

\text{Li}(x) = \int_2^x \frac{dt}{\ln t}

, which typically outperforms

\frac{x}{\ln x}

for finite values. The theorem also implies that the probability a randomly chosen integer near

x

is prime is roughly

\frac{1}{\ln x}

Worked Example

Problem: Estimate the number of primes less than or equal to 1,000,000 using the Prime Number Theorem, and compare with the true value.

Step 1: Compute the natural logarithm of 1,000,000.

\ln(10^6) = 6 \ln 10 \approx 6 \times 2.3026 = 13.8155

Step 2: Apply the approximation formula.

\frac{x}{\ln x} = \frac{1{,}000{,}000}{13.8155} \approx 72{,}382

Step 3: Compare with the exact count. The true value is π(1,000,000) = 78,498. The estimate undershoots by about 7.8%, which is typical — the approximation improves for larger x.

Answer: The Prime Number Theorem estimates about 72,382 primes up to one million, compared to the exact count of 78,498.

Why It Matters

The Prime Number Theorem is foundational in analytic number theory and directly influences the design of RSA encryption, where generating large primes depends on knowing how densely primes occur. It also motivates deeper conjectures like the Riemann Hypothesis, which would sharpen the error term in the prime-counting estimate.

Common Mistakes

Mistake: Treating the theorem as an exact formula rather than an asymptotic one.

Correction: The symbol ~ means the ratio π(x) / (x/ln x) → 1 as x → ∞. For any finite x, there will be a nonzero error. The theorem guarantees the relative error vanishes, not the absolute error.