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]istrue: - For
m = p * pup tonstepping byp: setisPrime[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: mark4, 6, 8, 10, 12, 14, 16, 18, 20p = 3: mark9, 12, 15, 18p = 4: already marked → skipp = 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, storespf[i]= smallest prime dividingi. To factorize anyx <= n, simply loopwhile (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
- Euler's Totient Function — computed for all $1..n$ using the same sieve idea.
- GCD & LCM — foundational number theory alongside prime sieves.