Sieve of Eratosthenes

The Sieve of Eratosthenes is one of the oldest known algorithms, devised by the Greek mathematician Eratosthenes of Cyrene around 240 BC. Eratosthenes -- the same scholar who famously estimated the circumference of the Earth -- created this method for finding all prime numbers up to any given limit. The algorithm works by systematically eliminating the multiples of each discovered prime, leaving behind only the prime numbers themselves. Despite being over two thousand years old, it remains the standard and most efficient method for generating lists of small to moderate-sized primes, a testament to the elegance and durability of well-designed algorithms.

Historical Context

Eratosthenes served as the chief librarian at the Library of Alexandria and was one of the most versatile scholars of the ancient world. His sieve was described by Nicomachus of Gerasa in his "Introduction to Arithmetic" around 100 AD. The name "sieve" comes from the metaphor of sifting through numbers -- composite numbers fall through the holes while primes are retained. The algorithm has been continuously used for over two millennia, making it arguably the longest-lived algorithm still in practical use today.

How It Works

1. Initialize: Create a list of numbers from 2 to n, all marked as potentially prime.
2. Find prime: The smallest unmarked number is prime.
3. Eliminate multiples: Mark all multiples of this prime as composite (not prime). As an optimization, start marking from p squared rather than 2p, because all smaller multiples have already been marked by smaller primes.
4. Advance: Move to the next unmarked number and repeat.
5. Stopping condition: Stop when the current prime exceeds the square root of n. Any remaining unmarked number must be prime, because if it had a factor other than 1 and itself, at least one of those factors would be at most the square root of n and would have been discovered already.

The square root optimization is the key insight. For n = 100, you only need to sieve with primes up to 10 (that is, 2, 3, 5, and 7). After eliminating their multiples, every unmarked number remaining is guaranteed to be prime.

Complexity

The time complexity of O(n log log n) arises from the harmonic series of reciprocals of primes: 1/2 + 1/3 + 1/5 + 1/7 + ... which grows as log log n. This makes the sieve remarkably efficient -- the log log n factor grows so slowly that log log(10^9) is only about 3. For all practical purposes, the sieve runs in nearly linear time relative to n.

Variants and Optimizations

The segmented sieve processes the range in blocks that fit in CPU cache, reducing memory usage from O(n) to O(square root of n) while maintaining the same time complexity. This variant can sieve ranges up to 10^12 or beyond. The sieve of Sundaram (1934) is an alternative that finds all odd primes using a different elimination pattern. The sieve of Atkin (2003) has a theoretically better asymptotic complexity of O(n / log log n) but is more complex to implement and only faster in practice for very large values of n.

When It's Used

The Sieve of Eratosthenes is the standard method for generating all primes up to a moderate limit, typically up to approximately 10^8 in a straightforward implementation. It is used extensively in number theory research, in cryptography for generating prime candidates for RSA and other public-key systems, in competitive programming where prime factorization or prime-counting problems are common, and in mathematical software libraries. For testing whether a single large number is prime, probabilistic tests like Miller-Rabin are preferred. The sieve also serves as a beautiful introduction to algorithmic thinking in education -- it demonstrates how a simple, systematic approach can solve a problem that seems inherently difficult.