🔢 Sieve of Eratosthenes
Invented around 240 BC by the ancient Greek mathematician Eratosthenes, this algorithm finds all primes up to a limit N. Starting from 2, it marks all multiples of each prime as composite — any number that survives unmarked is prime. Watch the pattern emerge: primes glow gold, composites dim, and you can see the Ulam spiral of primes and the prime gaps grow. The prime counting function π(x) ≈ x/ln(x) is shown below. 🇺🇦 Українська
View
The Prime Number Theorem
The Prime Number Theorem (1896, Hadamard & de la Vallée Poussin) states that π(x) ~ x/ln(x) as x → ∞. A sharper approximation is the logarithmic integral li(x) = ∫₂ˣ dt/ln(t). The sieve runs in O(N log log N) time — remarkably fast. The twin prime conjecture asks whether there are infinitely many primes p where p+2 is also prime; this remains unproven. The Riemann Hypothesis predicts the exact error term in π(x).