Prime Counting Function
Estimate how many prime numbers exist below a given value using the prime counting function and prime number theorem.
The Function
The prime counting function π(x) gives the exact count of prime numbers less than or equal to x. For example, π(10) = 4 because there are four primes up to 10: {2, 3, 5, 7}.
Computing π(x) exactly for large x is very expensive. The prime number theorem provides an elegant approximation that becomes more accurate as x grows.
Prime Number Theorem (Approximation)
As x grows large, the ratio π(x) / (x / ln(x)) approaches 1. This means primes thin out logarithmically — they become rarer but never stop appearing.
Better Approximation (Logarithmic Integral)
The logarithmic integral Li(x) gives a much closer estimate than x / ln(x). It was first proposed by Carl Friedrich Gauss when he was just 15 years old.
Variables
| Symbol | Meaning | Unit |
|---|---|---|
| π(x) | Number of primes less than or equal to x | count |
| x | Upper bound to count primes up to | positive integer |
| ln(x) | Natural logarithm of x | dimensionless |
| Li(x) | Logarithmic integral from 2 to x | count (approx) |
Example 1
Estimate the number of primes below 1,000,000 using x / ln(x)
x = 1,000,000
ln(1,000,000) = ln(10⁶) = 6 × ln(10) ≈ 6 × 2.3026 = 13.816
π(x) ≈ 1,000,000 / 13.816 ≈ 72,382
Estimate: ~72,382 primes. Actual value: π(10⁶) = 78,498 — about 8% error
Example 2
Estimate the number of primes below 100
x = 100
ln(100) = 2 × ln(10) ≈ 4.605
π(x) ≈ 100 / 4.605 ≈ 21.7
Estimate: ~22 primes. Actual value: π(100) = 25 — the approximation improves for larger x
Known Values of π(x)
| x | π(x) Exact | x / ln(x) |
|---|---|---|
| 100 | 25 | 22 |
| 1,000 | 168 | 145 |
| 10,000 | 1,229 | 1,086 |
| 1,000,000 | 78,498 | 72,382 |
| 1,000,000,000 | 50,847,534 | 48,254,942 |
When to Use It
- Estimating the density of prime numbers in a given range
- Cryptography — understanding how many primes are available for key generation
- Algorithm analysis — estimating the cost of prime-related computations
- Number theory research and mathematical competitions
- Understanding the distribution and patterns of prime numbers