mathlib documentation

number_theory.prime_counting

The Prime Counting Function #

In this file we define the prime counting function: the function on natural numbers that returns the number of primes less than or equal to its input.

Main Results #

The main definitions for this file are

We then prove that these are monotone in nat.monotone_prime_counting and nat.monotone_prime_counting'. The last main theorem nat.prime_counting'_add_le is an upper bound on π' which arises by observing that all numbers greater than k and not coprime to k are not prime, and so only at most φ(k)/k fraction of the numbers from k to n are prime.

Notation #

We use the standard notation π to represent the prime counting function (and π' to represent the reindexed version).

A variant of the traditional prime counting function which gives the number of primes strictly less than the input. More convenient for avoiding off-by-one errors.

Equations
def nat.prime_counting (n : ) :

The prime counting function: Returns the number of primes less than or equal to the input.

Equations
@[simp]
theorem nat.prime_counting'_add_le {a k : } (h0 : 0 < a) (h1 : a < k) (n : ) :

A linear upper bound on the size of the prime_counting' function