Prime counting 2026-10-20
Prime counting evaluates the prime-counting function: it determines how many prime numbers do not exceed a given bound. A number-theoretic sieve can construct the whole table up to a moderate bound, while methods such as the Lehmer prime-counting algorithm group whole classes of integers to evaluate much larger arguments without listing every prime number.
Prime-counting function Created 2026-09-24 Updated 2026-11-05
The prime-counting function counts the prime numbers not exceeding a real bound :
Thus , and . It is a nondecreasing step function with a jump of one at each prime number, and for .
Computing one large value is different from listing every prime number below it. A number-theoretic sieve can do both up to a moderate bound; Legendre prime-counting formula and the Lehmer prime-counting algorithm instead organize counts of allowable factors. The Prime number theorem describes the long-term scale , rather than exact individual jump locations.