The prime-counting function and the prime number theorem

Sieves all primes up to 100,000 and compares the prime-counting function \(\pi(n)\) against the prime number theorem’s approximation \(n/\ln n\).

import math

from mathematicskit.number_theory import is_prime_miller_rabin, sieve_of_eratosthenes
from mathematicskit.number_theory.visualizers.plots import plot_prime_counting

Sieve and count

primes = sieve_of_eratosthenes(100000)
print(f"pi(100000) = {len(primes)} (prime number theorem estimate: {100000 / math.log(100000):.1f})")

pi(100000) = 9592 (prime number theorem estimate: 8685.9)

Cross-check the largest sieved prime with Miller-Rabin

largest = int(primes[-1])
print(f"largest prime found: {largest}, Miller-Rabin agrees: {is_prime_miller_rabin(largest)}")

largest prime found: 99991, Miller-Rabin agrees: True

Plot pi(n) vs. the prime number theorem approximation

plot_prime_counting(2000)

<Axes: title={'center': 'Prime-counting function'}, xlabel='n', ylabel='number of primes <= n'>