Sieve of Eratosthenes, prime gaps, Ulam spiral, and π(x) vs Li(x)
400
—
Prime Count
—
Density
—
Largest Prime
The Sieve of Eratosthenes (~240 BC) finds all primes up to N in O(N log log N). The prime number theorem states π(x) ~ x/ln(x) — but Gauss's logarithmic integral Li(x) = ∫₂ˣ dt/ln(t) is a far better approximation.
The Ulam spiral (1963) reveals unexpected diagonal alignments of primes. Largest known prime gap below 2000: between twin primes and highly composite numbers.