AntInLoop

Sieve of Eratosthenes

The Sieve of Eratosthenes finds all prime numbers up to n in near-linear O(n log log n) time by iteratively marking multiples of each prime starting from p^2.

Difficulty: Easy · Interactive Visualizer · C++ / Python / Java / JS Code

Sieve of Eratosthenes

The Sieve of Eratosthenes finds all prime numbers up to $n$ in $O(n \log \log n)$ time—virtually linear! Starting from 2, whenever it encounters an unmarked number p, it marks all multiples p^2, p^2 + p, p^2 + 2p, ... as composite. By storing the Smallest Prime Factor (SPF) instead of a boolean, the same sieve also factorizes any number $\le n$ in $O(\log n)$ time!

At a Glance

| Property | Value |

| :--- | :--- |

| Time Complexity | $O(n \log \log n)$ |

| Auxiliary Space | $O(n)$ (or $O(\sqrt{R})$ for Segmented Sieve on $[L, R]$) |

| Loop Start Optimization | Start marking at *p p** (all smaller multiples $k \cdot p$ with $k < p$ are already marked!) |

| Best Used When | Generating primes up to $10^7$, fast $O(\log n)$ prime factorization (SPF), segmented primes in $[L, R]$ |

---

How It Works

1. Create a boolean array isPrime[0..n] initialized to true, with isPrime[0] = isPrime[1] = false.

2. For p = 2 while p * p <= n:

  • If isPrime[p] is true:
  • For m = p * p up to n stepping by p: set isPrime[m] = false.

3. Every index i still marked true is prime!

procedure sieve(n):
    isPrime = array of size n + 1 filled with true
    isPrime[0] = isPrime[1] = false
    for p = 2 while p * p <= n:
        if isPrime[p]:
            for m = p * p to n step p:
                isPrime[m] = false
    return all i where isPrime[i] is true

Step-by-Step Trace ($n = 20$)

  • p = 2: mark 4, 6, 8, 10, 12, 14, 16, 18, 20
  • p = 3: mark 9, 12, 15, 18
  • p = 4: already marked → skip
  • p = 5: $5^2 = 25 > 20$ → stop!
  • Remaining Primes: 2, 3, 5, 7, 11, 13, 17, 19.

---

Complexity & Key Insights

  • Why $O(n \log \log n)$: The total inner-loop work is $\sum_{p \le n} \frac{n}{p} = n \sum_{p \le n} \frac{1}{p} \approx n \ln \ln n$ by Mertens' second theorem! For $n = 10^7$, $\ln \ln n \approx 2.8$.
  • SPF Sieve ($O(\log n)$ Factorization): Instead of a bool, store spf[i] = smallest prime dividing i. To factorize any x <= n, simply loop while (x > 1) { factor = spf[x]; x /= spf[x]; }!
  • Segmented Sieve for Huge Ranges ($L, R \le 10^{12}$, $R - L \le 10^6$): Precompute base primes up to $\sqrt{R}$ with a regular sieve, then mark multiples only inside the window [L, R] in $O((R - L) \log \log R + \sqrt{R})$ time!

---

Practice Problems

Easy

1. Count Primes Strictly Less Than $n$ (LeetCode 204)

Return the number of prime numbers strictly less than n.

Approach: Classic Sieve of Eratosthenes marking from p * p. Time: $O(n \log \log n)$. Space: $O(n)$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <vector>

int countPrimes(int n) {
    if (n <= 2) return 0;
    std::vector<bool> isPrime(n, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; 1LL * p * p < n; ++p) {
        if (isPrime[p]) {
            for (int m = p * p; m < n; m += p) isPrime[m] = false;
        }
    }
    int count = 0;
    for (int i = 2; i < n; ++i) if (isPrime[i]) ++count;
    return count;
}

int main() {
    std::cout << countPrimes(10) << " " << countPrimes(100) << "\n"; // 4 25
    return 0;
}

</details>

2. Smallest Prime Factor (SPF) Sieve for $O(\log x)$ Factorization

Preprocess up to N so any query factorize(x) returns the prime factorization of x in $O(\log x)$ time.

Approach: Initialize spf[i] = i; whenever spf[p] == p, set spf[m] = p for unmarked multiples m = pp, pp+p, .... Time: $O(N \log \log N)$ build, $O(\log x)$ per query.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <numeric>
#include <vector>

std::vector<int> buildSPF(int n) {
    std::vector<int> spf(n + 1);
    std::iota(spf.begin(), spf.end(), 0);
    for (int p = 2; 1LL * p * p <= n; ++p) {
        if (spf[p] == p) {
            for (int m = p * p; m <= n; m += p) {
                if (spf[m] == m) spf[m] = p;
            }
        }
    }
    return spf;
}

std::vector<int> factorize(int x, const std::vector<int>& spf) {
    std::vector<int> factors;
    while (x > 1) {
        factors.push_back(spf[x]);
        x /= spf[x];
    }
    return factors;
}

int main() {
    auto spf = buildSPF(1000);
    for (int f : factorize(360, spf)) std::cout << f << " ";
    std::cout << "\n"; // 2 2 2 3 3 5
    return 0;
}

</details>

---

Intermediate

3. Segmented Sieve (Primes in Range $[L, R]$ up to $10^{12}$)

Find all primes in [L, R] where $1 \le L \le R \le 10^{12}$ and $R - L \le 10^6$.

Approach: Sieve base primes up to $\lfloor \sqrt{R} \rfloor$. For each base prime p, compute the first multiple in [L, R] as max(p p, ((L + p - 1) / p) p) and mark multiples inside isPrimeSeg[0..R-L]. Time: $O((R - L + \sqrt{R}) \log \log R)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

std::vector<long long> segmentedSieve(long long L, long long R) {
    long long lim = static_cast<long long>(std::sqrt(R)) + 1;
    std::vector<bool> base(lim + 1, true);
    std::vector<long long> primes;
    for (long long i = 2; i <= lim; ++i) {
        if (base[i]) {
            primes.push_back(i);
            for (long long m = i * i; m <= lim; m += i) base[m] = false;
        }
    }

    std::vector<bool> seg(R - L + 1, true);
    if (L == 1) seg[0] = false;
    for (long long p : primes) {
        long long start = std::max(p * p, ((L + p - 1) / p) * p);
        for (long long m = start; m <= R; m += p) seg[m - L] = false;
    }

    std::vector<long long> res;
    for (long long i = 0; i <= R - L; ++i) {
        if (seg[i]) res.push_back(L + i);
    }
    return res;
}

int main() {
    for (long long p : segmentedSieve(100, 120)) std::cout << p << " ";
    std::cout << "\n"; // 101 103 107 109 113
    return 0;
}

</details>

4. Count Divisors for All Numbers $1..N$ via Sieve

Compute divCount[i] (number of divisors of i) for every $1 \le i \le N$ in $O(N \log N)$ time.

Approach: Instead of trial-dividing every number, iterate d = 1..N and increment divCount[m] for every multiple m = d, 2d, 3d, ... <= N! Total work is the harmonic sum $N \sum_{d=1}^N \frac{1}{d} = O(N \log N)$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <vector>

std::vector<int> countDivisorsUpTo(int n) {
    std::vector<int> divs(n + 1, 0);
    for (int d = 1; d <= n; ++d) {
        for (int m = d; m <= n; m += d) ++divs[m];
    }
    return divs;
}

int main() {
    auto d = countDivisorsUpTo(12);
    for (int i = 1; i <= 12; ++i) std::cout << i << ":" << d[i] << " ";
    std::cout << "\n";
    return 0;
}

</details>

---

Hard

5. Linear Sieve (Euler's Sieve in Exact $O(n)$ Time)

Generate all primes and smallest prime factors up to $n$ in strictly $O(n)$ time by marking each composite number exactly once (via its smallest prime factor).

Approach: Maintain the list primes. For each i = 2..n, if spf[i] == 0, set spf[i] = i and append i to primes. Then for each p in primes with p <= spf[i] and i p <= n, set spf[i p] = p—breaking when p == spf[i] guarantees every composite is visited exactly once! Time: $O(n)$. Space: $O(n)$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <vector>

std::vector<int> linearSieve(int n) {
    std::vector<int> spf(n + 1, 0), primes;
    for (int i = 2; i <= n; ++i) {
        if (spf[i] == 0) {
            spf[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > spf[i] || 1LL * i * p > n) break;
            spf[i * p] = p;
        }
    }
    return primes;
}

int main() {
    auto primes = linearSieve(30);
    for (int p : primes) std::cout << p << " ";
    std::cout << "\n";
    return 0;
}

</details>

---

Related Algorithms