Sieve of Eratosthenes

The Sieve of Eratosthenes is one of the oldest and most elegant algorithms in computer science, dating back to ancient Greece (~240 BC). It efficiently finds all prime numbers up to a given limit n by iteratively marking the multiples of each prime as composite (non-prime).

#1.1 Core Idea

Start with all numbers marked as prime. For each prime p found, mark all its multiples (starting from p²) as not prime. Whatever remains unmarked is a prime.

This simple "sieving" process eliminates composites in bulk — that's what makes it fast.

#1.2 Step-by-Step Example

Let's find all primes up to n = 30:

Initial:  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

Step 1 (p=2): Mark 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 ❌
Step 2 (p=3): Mark 9, 15, 21, 27 ❌
Step 3 (p=5): Mark 25 ❌
Step 4 (p=7): 7² = 49 > 30, so stop.

✅ Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Sieve of Eratosthenes

#1.3 Implementation

Python

def sieve_of_eratosthenes(n: int) -> list[int]:
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0 and 1 are not prime
 
    p = 2
    while p * p <= n:
        if is_prime[p]:
            # Mark all multiples of p starting from p²
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
        p += 1
 
    return [i for i, prime in enumerate(is_prime) if prime]
 
# Example
print(sieve_of_eratosthenes(30))
# Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

JavaScript

function sieveOfEratosthenes(n) {
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
 
  for (let p = 2; p * p <= n; p++) {
    if (isPrime[p]) {
      for (let multiple = p * p; multiple <= n; multiple += p) {
        isPrime[multiple] = false;
      }
    }
  }
 
  return isPrime.reduce((primes, val, idx) => {
    if (val) primes.push(idx);
    return primes;
  }, []);
}
 
console.log(sieveOfEratosthenes(30));
// Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

C++

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
 
    for (int p = 2; (long long)p * p <= n; p++) {
        if (is_prime[p]) {
            for (int multiple = p * p; multiple <= n; multiple += p)
                is_prime[multiple] = false;
        }
    }
 
    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) primes.push_back(i);
 
    return primes;
}

#1.4 Complexity Analysis

Why p * p? When we reach p, all smaller multiples of p (like 2p, 3p, ...) have already been marked by earlier primes. So we safely start from p².

#1.5 Common DSA Use Cases

The Sieve is frequently used as a preprocessing step in competitive programming and DSA problems:

• Finding prime factors — precompute smallest prime factor (SPF) sieve
• Counting primes in a range — prefix sum over sieve array
• Goldbach's conjecture problems — express even numbers as sum of two primes
• Prime sums / products — precomputed prime list speeds lookups
• Segmented Sieve — for very large n where memory is a concern

#1.6 Variants

1.6.1 Segmented Sieve

Used when n is very large (e.g., n = 10¹²). Divides the range into segments of size √n and applies the sieve segment by segment, keeping memory usage at O(√n).

1.6.2 Linear Sieve

A modification that achieves O(n) time by ensuring each composite is crossed out exactly once using the smallest prime factor technique.

def linear_sieve(n):
    lp = [0] * (n + 1)   # Smallest prime factor
    primes = []
 
    for i in range(2, n + 1):
        if lp[i] == 0:
            lp[i] = i
            primes.append(i)
        for p in primes:
            if p > lp[i] or i * p > n:
                break
            lp[i * p] = p
 
    return primes

#1.7 Limitations

• Memory intensive for very large n (e.g., n = 10⁹ requires ~1 GB for a bool array). Use a segmented or bitset sieve in such cases.
• Not suitable for checking a single large number — use Miller-Rabin primality test instead.

#1.8 Summary

Pro Tip: In competitive programming, precompute the sieve at the start
for the maximum constraint (n = 10^6 or 10^7), then answer all prime-related queries in O(1).

#1.8 Sources

Source: GeeksforGeeks - Sieve of Eratosthenes

Leetcode : 2523. Closest Prime Numbers in Range