Sieve of Eratosthenes & prime factorization
Scenario
You need to find all prime numbers up to 1,000,000. If you write a loop checking every number `i` by dividing it by every number from 2 to `sqrt(i)`, the program will take too long and fail.
How can you instantly identify all primes in a massive range without doing any division?
Why it exists
Number theory is a heavy component of mathematical programming and cryptography. Finding primes and prime factors is the foundation for calculating common divisors and understanding large-scale numerical patterns. The Sieve of Eratosthenes provides an elegant, near-linear time pre-computation table that transforms O(sqrt(N)) prime-checking into O(1) lookups.
Mental model
Imagine you have a list of numbers from 2 to 100. You circle 2 (it's prime), then aggressively cross out every multiple of 2 (4, 6, 8...). You then move to the next uncrossed number (3), circle it, and cross out all multiples of 3. By the end, the uncrossed numbers are exactly the primes.
The Sieve of Eratosthenes is an ancient, highly optimized algorithm (O(N log log N)) used to generate all prime numbers up to a limit `N`. Instead of testing if a number is prime (division), it iteratively crosses out composites (multiplication/addition).
Explanation
**The Sieve of Eratosthenes:**
We create a boolean array `is_prime` of size `N+1`, initialized to `true`. We start at 2. If `is_prime[2]` is true, we iterate through its multiples (4, 6, 8...) and mark them `false`. We proceed to the next true number, and repeat.
*Optimization 1:* We only need to check numbers up to `sqrt(N)`. Every composite number up to `N` must have at least one prime factor `<= sqrt(N)`. Thus, checking primes up to `sqrt(N)` safely crosses out all composites up to `N`.
*Optimization 2:* When crossing out multiples for a prime `p`, we can start crossing out at `p * p`. All smaller multiples (`p * 2`, `p * 3`) were already crossed out by smaller primes.
**Prime Factorization (O(sqrt(N))):**
To find the prime factors of a single number `N`, we don't need the Sieve. We just loop `d` from 2 to `sqrt(N)`. While `N` is divisible by `d`, we add `d` to our factors and divide `N` by `d`. If `N > 1` at the very end, that leftover `N` is itself a prime factor.
*(Note: If you need to factorize 100,000 different numbers, you can modify the Sieve to store the Smallest Prime Factor (SPF) for each number. To factorize, repeatedly divide the query number by its SPF (`N = N / SPF[N]`) until it becomes 1. This takes O(log N) time per query!)*
**Space Complexity Warning:**
The Sieve requires `O(N)` memory. An array of size 10^9 requires ~1GB of RAM, exceeding typical limits. The standard Sieve is only viable up to `N ~ 10^7`.
Code examples
Sieve of Eratosthenes
vector<bool> sieve(int n) {
vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;
// Optimization 1: Loop up to sqrt(n)
for (int p = 2; p * p <= n; p++) {
if (is_prime[p]) {
// Optimization 2: Start crossing out at p*p
for (int i = p * p; i <= n; i += p) {
is_prime[i] = false;
}
}
}
return is_prime;
}This computes all primes up to N in O(N log log N) time, which is practically linear. `N = 10^7` computes in fractions of a second.
Prime Factorization of a Single Number
vector<long long> prime_factors(long long n) {
vector<long long> factors;
for (long long d = 2; d * d <= n; d++) {
while (n % d == 0) {
factors.push_back(d);
n /= d;
}
}
// If n is a prime greater than the loop limit
if (n > 1) {
factors.push_back(n);
}
return factors;
}Calculates the prime factors of N in O(sqrt(N)) time. This works efficiently for isolated numbers up to 10^14.
Key points
- Sieve for ranges, division for instances: Use the Sieve when you need all primes up to N. Use the O(sqrt(N)) loop when you only need to factorize a single number.
- The sqrt(N) boundary: Every composite number N has at least one prime factor less than or equal to sqrt(N).
Common mistakes
- Forgetting the leftover prime in factorization: When doing the O(sqrt(N)) factorization, beginners often forget the `if (n > 1)` check at the end. For example, if `N = 14`, the loop extracts `2`, leaving `N = 7`. The loop terminates because `3*3 > 7`. Without the final check, you lose the factor `7`.
Recall questions
- What is the time complexity of the Sieve of Eratosthenes?
- In the Sieve, why is it safe to start marking composite numbers at `p * p` instead of `p * 2`?
- What is the time complexity to find the prime factors of a single, isolated number without a pre-computed sieve?
Questions & answers
A developer runs the Sieve of Eratosthenes up to `N = 10^9`. Their code gets a 'Memory Limit Exceeded' error, or a Segmentation Fault. Why?
An array of size 10^9 requires massive contiguous memory allocation. Even as a `vector<bool>` (which optimizes to 1 bit per boolean), it requires ~125 MB, and standard arrays would require 1-4 GB. The standard Sieve should only be used for N up to ~10^7.
Approach: Recognize the space complexity constraints of O(N) memory algorithms.
You are given 100,000 queries, each asking for the prime factorization of a number up to 10^7. Using the O(sqrt(N)) factorization loop for each query results in TLE. How can you optimize this?
Modify the Sieve of Eratosthenes to store the Smallest Prime Factor (SPF) for every number up to 10^7. Then, for each query, repeatedly divide the number by its SPF. This reduces factorization from O(sqrt(N)) to O(log N) per query.
Approach: Understand how to augment standard algorithms for bulk querying.