Back to Study Material Data Structures and Algorithms

Sieve of Eratosthenes

The Sieve of Eratosthenes is one of the oldest known algorithms, attributed to the ancient Greek mathematician Eratosthenes of Cyrene, yet it remains among...

Sieve of Eratosthenes

The Classic Sieve and Its Time Complexity Analysis

The Sieve of Eratosthenes is one of the oldest known algorithms, attributed to the ancient Greek mathematician Eratosthenes of Cyrene, yet it remains among the most practically efficient methods for finding all primes up to a given limit N. The algorithm initializes a boolean array of size N+1 with all entries true, then iterates from 2 upward. For each number p that is still marked true (prime), it marks all multiples of p starting from p*p as composite. After the iteration, all remaining true entries are prime.

The time complexity of the basic sieve is O(N log log N), which arises from the sum of N/p over all primes p up to N. This sum converges slowly due to the divergence of the sum of reciprocals of primes, yielding the log log N factor. In practice, for N = 10^7 the sieve runs in roughly 50 milliseconds in C++ with cache-friendly memory access, making it suitable for most competitive programming constraints.

The space complexity is O(N) for the boolean array. You can reduce memory by a factor of eight by using a bitset instead of a byte array, since each entry is conceptually a single bit. In C++, std::bitset<N> or a manually managed bit array halves cache pressure and roughly doubles throughput for large N. For N up to 10^8, a bitset sieve is typically necessary to stay within a 256 MB memory limit.

Segmented Sieve for Large Ranges and Memory Constraints

The standard sieve becomes impractical when N exceeds roughly 10^8 due to memory constraints. The segmented sieve addresses this by dividing the range [2, N] into segments of size approximately sqrt(N) and processing each segment independently. First, you run a standard sieve up to sqrt(N) to find all small primes. Then, for each segment [lo, hi], you initialize a local boolean array and cross off multiples of each small prime within the segment.

The segmented sieve uses only O(sqrt(N)) memory for the small primes and O(sqrt(N)) for the current segment buffer, independent of N. Its time complexity remains O(N log log N), matching the standard sieve asymptotically. In practice, the segmented version processes each cache-sized segment entirely within L1 or L2 cache, which can make it faster than the standard sieve for large N due to improved cache behavior.

Implementation requires careful bookkeeping: for each small prime p, you need to know where to start crossing off multiples in the current segment. The starting offset within [lo, hi] for prime p is ceil(lo / p) * p if that value is greater than p, otherwise p * p. One common implementation error is starting at lo / p * p and accidentally including p itself as composite. Always ensure the starting offset is at least p^2 or lo, whichever is larger.

Variants: Linear Sieve, Smallest Prime Factor Sieve, and Applications

The linear sieve, also called the Euler sieve, achieves O(N) time by ensuring each composite number is marked exactly once — by its smallest prime factor. The algorithm maintains a list of found primes and, for each i from 2 to N, marks i * primes[j] as composite for each prime primes[j] in the list, stopping as soon as primes[j] divides i. This prevents redundant marking and achieves truly linear time, though with a slightly larger constant than the Eratosthenes sieve due to list management overhead.

The smallest prime factor (SPF) sieve is a natural extension of either sieve where instead of storing a boolean, you store the smallest prime factor of each number. During the marking step, if spf[i * p] has not been set yet, assign spf[i * p] = p. Once the SPF array is built, factorizing any number n up to N takes O(log n) time: repeatedly divide n by spf[n] until n reaches 1.

Practical applications of sieve-based precomputation are numerous. Computing Euler's totient for all numbers up to N uses a sieve-like approach: initialize phi[i] = i, then for each prime p, multiply phi[multiples of p] by (p - 1) / p. Computing the Mobius function, divisor sums, and Liouville's function all follow the same multiplicative sieve pattern. These precomputations enable O(1) or O(log n) answers to number-theoretic queries after O(N log log N) setup — a pattern that appears repeatedly in competitive programming.