Sieve of Eratosthenes

Number Theory · Axiom Academy

An ancient and elegant algorithm for finding all prime numbers up to any given limit We begin by listing all integers from 2 to n . The number 2 is the smallest prime. We keep 2 and mark all of its multiples (4, 6, 8, 10, ...) as composite. Key insight: Every even number greater than 2 is composite because it's divisible by 2. 2. Next Prime (3) and Its Multiples The next unmarked number is 3, which must be prime. We keep 3 and mark all of its multiples (6, 9, 12, 15, ...) as composite. Notice that 6 and 12 were already marked by 2. Pattern: The first unmarked multiple of 3 to mark is 3² = 9, since smaller multiples were already marked by 2. We continue this process with 5, 7, 11, and so on. A crucial optimization: we only need to continue until we reach √n. Any composite number less than n must have a prime factor ≤ √n. 4. Complete Algorithm and Complexity The complete algorithm is remarkably simple and elegant: The Sieve of Eratosthenes remains one of the most practical methods for generating lists of primes, and variations of this algorithm are still used in modern computational number theory.

This is the written version of the interactive lesson above. See the full Number Theory course.