Sieve of Eratosthenes — classical algorithm for finding primes

How the algorithm works

At its core the sieve maintains a table of boolean flags for the integers 2..n. The process proceeds in rounds:

1. Start with all numbers from 2 to n marked as "potentially prime."
2. Take the smallest number p that is still unmarked. It is a prime.
3. Mark every multiple of p greater than p (2p, 3p, 4p, ...) as composite.
4. Repeat step 2 until no unmarked numbers remain or until p exceeds n.

The numbers that remain unmarked at the end are the primes up to n.

Key optimization: start at p²

A standard improvement is to begin crossing out multiples of p at p² rather than 2p. This is safe because any smaller multiple kp (with k < p) has a factor k that is less than p, so that multiple would already have been marked when processing that smaller prime factor. Stopping the main loop when p² > n is also correct because no new composites can be generated from larger p.

Complexity and implementation notes

When implemented with simple arrays or bitsets, the sieve runs in roughly O(n log log n) time and requires O(n) space. Constants depend on details such as whether even numbers are stored (allowing a nearly twofold reduction in memory) and whether a bit-per-number representation is used. Practical implementations use memory-efficient bit arrays and skip obvious composites (for example, all even numbers) to improve speed.

Variants and practical uses

• Segmented sieve: divides the range into blocks to reduce peak memory usage and to handle very large n without storing all flags at once.
• Wheel factorization: pre-filters multiples of small primes (2, 3, 5, ...) to reduce the number of candidates and memory operations.
• Bitset optimizations and CPU cache-aware traversals: important in high-performance implementations.

Beyond listing primes for mathematical exploration, sieves are used as subroutines in factorization methods, in primality testing heuristics, in cryptographic key generation workflows (as a preparatory step), and in programming contests where many primes in a range are required.

Historical context and examples

The method is named after Eratosthenes of Cyrene, a Greek mathematician and librarian at Alexandria who lived in the 3rd century BCE. While the form used today is a modernized, algorithmic description, the underlying idea of eliminating multiples to reveal primes has ancient roots.

Example: to sieve up to 30, list 2..30, mark multiples of 2 (except 2), then mark multiples of 3 starting at 9, then 5 starting at 25; when p²>30 the process stops. The remaining unmarked numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

For further reading and implementations in many languages, see resources and code libraries referenced at Sieve of Eratosthenes and introductions to prime numbers.