The Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient and highly efficient algorithm for finding all prime numbers up to a specified limit. Devised by the Greek mathematician Eratosthenes of Cyrene in the 3rd century BC, it remains one of the most effective methods for generating primes in bulk.

Historical Background

Eratosthenes of Cyrene, who lived from roughly 276 to 194 BC, served as chief librarian at Alexandria and is better known for calculating the circumference of the Earth. None of his mathematical writings survive directly. The sieve reaches us through the Introduction to Arithmetic of Nicomachus of Gerasa, written around 100 AD, which describes the procedure and credits it to Eratosthenes.

The name is a metaphor for sifting. Nicomachus calls the procedure a koskinon, a sieve, because each pass lets the composites fall away and the primes are simply what stays behind. A frequently repeated embellishment has the composites pricked out of a wax tablet with a stylus, leaving a literally perforated sheet, but no ancient source describes the method that way, and the image appears to be a modern addition. What is not in doubt is that the procedure has survived unchanged in principle for more than two thousand years, which is unusual for an algorithm of any kind.

How the Algorithm Works

To find all primes less than or equal to a chosen integer n:

1. Create a list: Write down all consecutive integers from 2 through n.
2. Start with the smallest prime: Let p = 2, the first prime number.
3. Mark multiples: Cross out all multiples of p greater than p itself (i.e. 2p, 3p, 4p, ...). In practice, you can start crossing out from p² because smaller multiples will already have been marked.
4. Find the next unmarked number: Move to the smallest number greater than p that is not crossed out. That number is the next prime. Set p to this value.
5. Repeat or terminate: Repeat steps 3 and 4 until p² > n. When finished, all numbers remaining unmarked on the list are primes.

A Step-by-Step Example (Primes up to 30)

Suppose we want to find all primes up to 30:

• Initial List: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30.
• Multiples of 2: Strike out 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.
• Multiples of 3: Strike out 9, 15, 21, 27 (starting at 3² = 9; 6 is already marked).
• Multiples of 5: Strike out 25 (starting at 5² = 25; 10, 15, 20 are already marked).
• Next Prime is 7: Since 7² = 49 > 30, the algorithm stops.

The surviving numbers are the primes up to 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Notice how little work the later passes require. The pass for 2 marks 14 numbers, the pass for 3 marks only 4 that were not already struck, and the pass for 5 marks a single value. This diminishing return is what makes the algorithm fast, and it is the source of the unusual complexity figure given below.

Interactive Demo

Work through the sieve one action at a time. Each press of Next Step advances one action: it may select the next unmarked number as a prime, strike out one of its multiples, or announce that the current prime's pass is complete. Watch how often a later pass lands on a number that an earlier prime has already removed.

Why Does It Stop at √n?

Every composite number c ≤ n must have at least one prime factor less than or equal to √n. If it had only prime factors strictly greater than √n, their product would exceed n. Therefore, once we have eliminated the multiples of all primes up to √n, every remaining unmarked number must be prime.

The same reasoning explains why the inner loop can begin at p² rather than at 2p. Any multiple k · p with k < p has a smaller prime factor, so it was already removed during an earlier pass.

A Basic Implementation

The algorithm translates directly into code. This version returns every prime up to $n:

function sieve(int $n): array
{
    if ($n < 2) {
        return [];
    }

    $flags = array_fill(0, $n + 1, true);
    $flags[0] = false;
    $flags[1] = false;

    for ($p = 2; $p * $p <= $n; $p++) {
        if ($flags[$p]) {
            for ($m = $p * $p; $m <= $n; $m += $p) {
                $flags[$m] = false;
            }
        }
    }

    return array_keys(array_filter($flags));
}

The inner loop advances by repeated addition. Multiplication appears only in computing the starting point $p * $p and the loop bound, and no remainder operation appears anywhere in the procedure at all. Avoiding division is the central reason the sieve outperforms trial division.

Algorithmic Complexity

The time and memory complexity of the classic Sieve of Eratosthenes are:

• Time Complexity: O(n log(log n)) operations, making it extremely fast even for ranges in the tens of millions.
• Space Complexity: O(n) memory to store the boolean array of size n.

The log log n factor arises because the total marking work is the sum of n / p over all primes p up to √n, and that sum grows only as the double logarithm. In practical terms the factor is close to a small constant: it is about 3 for n around one billion, so the running time is nearly linear in the size of the range.

By comparison, testing each number separately by trial division costs on the order of √n divisions per candidate. Trial division is the better choice for a single large number, and probabilistic tests such as Miller-Rabin are better still. A sieve is usually the better choice when many primes in a range must be generated or counted, or when its composites must be marked.

Segmented Sieve & Modern Optimizations

For very large ranges where allocating an array for n elements exceeds available RAM, the Segmented Sieve processes the range in smaller blocks. It first generates the base primes up to √n; retaining those primes gives the standard O(√n) auxiliary-space bound. The segment length itself is tunable and can be chosen to suit the available memory and CPU cache while retaining the same fast time complexity.

Cache behaviour matters more than the operation count once the range grows large. A plain sieve over a billion entries strides through memory in steps of p, and once those strides exceed the cache line size almost every write becomes a cache miss. Sizing each segment to fit in the L1 or L2 cache keeps the working set resident and often yields a larger speedup than any reduction in the number of operations.

Two further optimizations are common. Storing one bit per candidate rather than one byte cuts memory by a factor of eight, and skipping even numbers halves it again, so a range of one billion needs roughly 60 MB instead of a gigabyte. Wheel factorization extends that idea by pre-excluding the multiples of the first few primes. A wheel based on 2, 3 and 5 stores only the 8 residues coprime to 30, which is under 27 percent of the range.

Related Sieves

• Sieve of Sundaram: Published in 1934, this method removes numbers of the form i + j + 2ij from the list of positive integers, then maps each survivor n to 2n + 1, which yields every odd prime. Doubling alone would only ever produce even numbers, so the increment is essential. It is elegant but offers no practical advantage.
• Sieve of Atkin: Introduced by A. O. L. Atkin and Daniel Bernstein in 2003. It uses quadratic forms and modular arithmetic to reach O(n / log log n) operations, though the larger constant factor means a well tuned Eratosthenes sieve usually beats it in practice.
• Linear sieve: A variant that marks each composite exactly once, giving true O(n) time and producing the smallest prime factor of every number as a side effect. Its irregular memory access often makes it slower in real use despite the better bound.
• Incremental sieve: A form that generates primes indefinitely without a fixed upper bound, typically implemented with a priority queue or a dictionary of upcoming composites. It suits generators and lazy sequences where the limit is not known in advance.

Practical Applications

Sieving remains standard wherever a table of small primes is needed. Factorization routines use a precomputed list for the trial division stage before switching to heavier methods. Cryptographic key generation sieves out candidates divisible by small primes before applying an expensive probabilistic test, which discards the great majority of composites cheaply. The general technique also underlies the quadratic sieve and the general number field sieve, the fastest known algorithms for factoring large integers.

Explore More Prime Number Topics

Test individual numbers on our Prime Number Check, read about how to check whether a number is prime, browse the first million primes, or learn more about the history of prime numbers.