Chapter 19
HomeThe naive approach checks every number individually — O(N√N). The Sieve of Eratosthenes marks multiples in a single pass, giving O(N log log N).
Start with a boolean array where all entries are "prime". For each number from 2 to √N, if it's still marked prime, mark all its multiples as non-prime. What's left are the primes.
vector<bool> sieve(int n) {
vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
return is_prime;
}
Start marking from i² — smaller multiples were already marked by smaller primes.
fn sieve(n: usize) -> Vec<bool> {
let mut is_prime = vec![true; n + 1];
is_prime[0] = false;
is_prime[1] = false;
let limit = (n as f64).sqrt() as usize;
for i in 2..=limit {
if is_prime[i] {
let mut j = i * i;
while j <= n {
is_prime[j] = false;
j += i;
}
}
}
is_prime
}
Once you've built the sieve, answering "is N prime?" is O(1) — just look it up in the boolean array.
auto primes = sieve(1000000); if (primes[n]) cout << "prime\n";
let primes = sieve(1_000_000);
if primes[n] { println!("prime"); }
💡 Start from i²
When marking multiples of 5, you might start at 10, 15, 20... But 2×5, 3×5 were already marked by 2 and 3. Starting from i² (5² = 25) avoids redundant work.