Sieve of Eratosthenes
Precompute primality and smallest prime factors once, then answer many prime-related queries cheaply.
Sieve of Eratosthenes
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
The sieve is the standard way to turn repeated prime questions into preprocessing. Instead of testing each number from scratch, I mark composite numbers once and reuse that work everywhere else.
When to Use It
Use a sieve when:
many primality or factorization queries are asked up to a common bound,
you need all primes up to \(n\),
multiplicative preprocessing starts from prime information.
Core Idea
Initialize every number as potentially prime, then iterate through the range. When a prime \(p\) is found, mark its multiples as composite. Each composite is crossed out because it has a smaller prime divisor.
Key Insight
The sieve wins because composite numbers are processed by structure rather than individually. After that, primality and smallest-prime-factor queries become array lookups.
Operations / Main Technique
build a boolean primality table,
optionally record the smallest prime factor of each number,
factor numbers quickly by repeatedly dividing by the stored smallest prime factor.
Worked example.
Once \(2\) is known prime, mark \(4, 6, 8, \ldots\). Once \(3\) is known prime, mark \(9, 12, 15, \ldots\). Numbers that survive all smaller prime marks are prime.
Correctness Intuition
Every composite number has a smallest prime divisor. When that prime is processed, the composite is marked. A prime is never marked by a smaller factor because none exists.
Complexity Analysis
classic sieve: \(O(n \log \log n)\),
linear smallest-prime-factor sieve: \(O(n)\),
one factorization using SPF: \(O(\log n)\) in practice.
Implementation
The reference code uses the linear sieve pattern because it naturally produces:
a list of primes,
a smallest-prime-factor array,
fast factorization support afterward.
Common Pitfalls
Choosing a bound that is too small for later queries.
Forgetting that the sieve is preprocessing, so it only helps if many queries share one limit.
Using too much memory when the bound is very large.
Confusing primality with smallest prime factor \(= 0\) or \(= i\) depending on the implementation.
Variants / Extensions
Segment sieve for a large interval \([L, R]\).
Euler phi and Mobius preprocessing.
Prime-counting prefix arrays on top of the primality table.
Practice Problems
Answer many primality queries.
Factor all array values up to a fixed limit.
Precompute multiplicative functions for many numbers.
References
Code
Contest-ready reference implementation for the idea explained above.
struct PrimeSieve {
int limit;
vector<int> primes;
vector<int> spf;
explicit PrimeSieve(int limit) : limit(limit), spf(limit + 1, 0) {
for (int i = 2; i <= limit; ++i) {
if (spf[i] == 0) {
spf[i] = i;
primes.push_back(i);
}
for (int p : primes) {
if (p > spf[i] || 1LL * i * p > limit) {
break;
}
spf[i * p] = p;
}
}
}
bool is_prime(int x) const {
return x >= 2 && spf[x] == x;
}
vector<pair<int, int>> factorize(int x) const {
vector<pair<int, int>> factors;
while (x > 1) {
int p = spf[x];
int cnt = 0;
while (x % p == 0) {
x /= p;
++cnt;
}
factors.push_back({p, cnt});
}
return factors;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.