Prime Number Theorem Explained with Worked Examples

The prime number theorem says that the number of primes up to satisfies : the ratio of the two sides tends to 1 as .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Prime number theorem means

Roughly, a random number near is prime with probability . So among the first 100 numbers about are prime (the true count is 25), among the first 1000 about 144.8 (true 168), and among the first million about 72382 (true 78498). The approximation is always a little low, but the ratio improves slowly: 1.15 at 100, 1.16 at 1000, 1.084 at a million. The logarithm is the one in the natural logarithm integral and the definition of e.

The theorem was proved in 1896 by Hadamard and de la Vallée Poussin, using the complex zeta function from the Euler product for the zeta function, which encodes the primes through prime factorisation. The sum of the reciprocals of the primes diverges like , a refinement of the growth of the harmonic series.

A better estimate is the logarithmic integral . The theorem gives the size of the th prime, , and explains how many primes there are to test in cryptography such as RSA. Arithmetic functions behind these results are handled with Möbius inversion.

What is it used for?

The theorem says primes thin out like one over the logarithm, so their count can be estimated without listing them.

How to use prime number theorem

  1. Choose the bound and compute .
  2. Divide: .
  3. Compare with the true count if known.
  4. Form the ratio to see how close the estimate is.

Graph

The estimate x / ln x for the number of primes up to xx = 100: 21.7 (true 25)102030405060708090100051015202530The estimate x / ln x for the number of primes up to xxestimatex / ln xGraph with x from 2 to 100 and y from 0 to 30. Shows the curve x / ln x; point x = 100: 21.7 (true 25) at (100, 21.71).

The estimate grows slowly and stays a little below the true count.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: primes up to 100

Estimate with ; the true value is 25.

Worked example
Answer
21.7121.71
  1. ln 100
  2. Estimate

Example 2: primes up to 1000

Estimate ; the true value is 168.

Worked example
Answer
144.76144.76
  1. ln 1000
  2. Estimate

Example 3: one million

Find the ratio of the true count to .

Worked example
Answer
1.08451.0845
  1. Ratio

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

x = 100

x/ln x ≈ 21.7 vs π(100) = 25

Underestimates.

x = 1000

144.8 vs π(1000) = 168

Ratio 0.862.

x = 10⁶

72 382 vs 78 498

Ratio 0.922.

Density

chance a number near x is prime ≈ 1/ln x

x = 1000: 0.145.

Word problems

The prime number theorem states π(x) ~ x/ln x: the number of primes up to x is asymptotically x/ln x, so the density of primes near x is about 1/ln x. The ratio π(x)/(x/ln x) tends to 1 slowly.

x = 100

Estimate π(100) with x/ln x.

  1. ln 1004.605
  2. 100 ÷ 4.60521.7
  3. Check: actual 25 ✓21.7.

x = 1000

Estimate π(1000).

  1. 1000 ÷ 6.908
  2. Check: actual 168 ✓144.8.

Ratio Higher

Find π(1000)/(x/ln x) with π(1000) = 168.

  1. 168 ÷ 144.8
  2. Check: 1.16 ✓1.16.

Density Higher

What is the chance a random number near 1000 is prime?

  1. 1/ln 1000
  2. Check: 14.5% ✓0.145.

Common mistakes

Using log₁₀

100/log₁₀ 100 = 50 ✗

100/ln 100 = 21.7 ✓

Natural logarithm.

Expecting equality

π(x) = x/ln x ✗

π(x) ~ x/ln x ✓

Asymptotic only.

Confusing π(x) with 3.14159

π = 3.14 ✗

prime counting function ✓

Different π.

Using x ln x

x ln 100 ✗

x/ln x ✓

Divide, do not multiply.

Exam tips

  1. π(x) ≈ x/ln x.
  2. Natural log.
  3. Density 1/ln x.
  4. li(x) is closer.
  5. Ratio → 1 slowly.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. ln(100) to 3 d.p. Foundation

4.605

2. 10000/ln(10000) to 1 d.p. Foundation

1085.7

3. 1/ln(100) to 3 d.p. Foundation

0.217

4. x/ln x for x = 50 to 1 d.p. Higher

12.8

5. x/ln x for x = 10 to 2 d.p. Higher

4.34

6. x/ln x for x = 500 to 1 d.p. Higher

80.5

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Prime counting function (π(x))
Number of primes ≤ x.
Prime number theorem
π(x) ~ x/ln x.
Asymptotic (~)
Ratio tends to 1.
Density of primes
About 1/ln x near x.
Natural logarithm
ln.
Logarithmic integral
li(x), a better estimate.

Frequently asked questions

What is the prime number theorem?

π(x) ~ x/ln x.

How many primes below 100?

25; the estimate gives 21.7.

What is the density of primes near x?

About 1/ln x.

Does π(x) equal x/ln x?

No, only asymptotically.

Which page covers Möbius inversion?

Möbius inversion.

Which page covers quadratic reciprocity?

quadratic reciprocity.

More in Discrete maths and number theory and the formula sheets.