x = 100
x/ln x ≈ 21.7 vs π(100) = 25
Underestimates.
The prime number theorem says that the number of primes up to satisfies : the ratio of the two sides tends to 1 as .
This page is easier if you are comfortable with:
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.
The theorem says primes thin out like one over the logarithm, so their count can be estimated without listing them.
The estimate grows slowly and stays a little below the true count.
These examples are worked by hand, step by step, so you can compare your own working.
Estimate with ; the true value is 25.
Estimate ; the true value is 168.
Find the ratio of the true count to .
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
x/ln x ≈ 21.7 vs π(100) = 25
Underestimates.
144.8 vs π(1000) = 168
Ratio 0.862.
72 382 vs 78 498
Ratio 0.922.
chance a number near x is prime ≈ 1/ln x
x = 1000: 0.145.
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.
Estimate π(100) with x/ln x.
Estimate π(1000).
Find π(1000)/(x/ln x) with π(1000) = 168.
What is the chance a random number near 1000 is prime?
π(x) = x/ln x ✗
π(x) ~ x/ln x ✓
Asymptotic only.
π = 3.14 ✗
prime counting function ✓
Different π.
x ln 100 ✗
x/ln x ✓
Divide, do not multiply.
Try each one on paper, then open the answer. Use the solver above to see the full working.
4.605
1085.7
0.217
12.8
4.34
80.5
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
π(x) ~ x/ln x.
25; the estimate gives 21.7.
About 1/ln x.
No, only asymptotically.
Möbius inversion.
More in Discrete maths and number theory and the formula sheets.