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.
The prime index of a prime number is its position in the increasing sequence . Thus the index of is , and the prime-counting function satisfies .
Indexing begins at one here. An implementation using zero-based array positions must subtract one. The index describes ordering among primes, whereas a prime gap measures the numerical distance between neighboring primes. For nonprime , still counts primes up to , but itself has no prime index.
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.
A prime counting algorithm that evaluates by recursively counting integers not divisible by the first few primes and correcting for products of larger primes. A small number-theoretic sieve and cached recursive values allow it to handle inputs much larger than the precomputed table.
For , let be the primes at most . The inclusion-exclusion principle counts unsieved positive integers by . These are and the remaining primes, since every composite number has a prime factor at most its square root. Hence for . This is a prime-counting identity, distinct from the Legendre formula for factorial valuations.
If for every , where , then
for . Every prime in contributes at least to the primorial, so
Taking logarithms, using , and observing that for proves the claim.

Articles by others on the same topic (1)

The prime-counting function, denoted as \( \pi(x) \), is a mathematical function that counts the number of prime numbers less than or equal to a given number \( x \).