# 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

• Nat.primeCounting: The prime counting function π
• Nat.primeCounting': π(n - 1)

We then prove that these are monotone in Nat.monotone_primeCounting and Nat.monotone_primeCounting'. The last main theorem Nat.primeCounting'_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
Instances For

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

Equations
Instances For

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

Equations
Instances For

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
Instances For
@[simp]
@[simp]
theorem Nat.prime_nth_prime (n : ) :

The cardinality of the finset primesBelow n equals the counting function primeCounting' at n.

theorem Nat.primeCounting'_add_le {a : } {k : } (h0 : 0 < a) (h1 : a < k) (n : ) :
Nat.primeCounting' (k + n) + * (n / a + 1)

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