Sieve of Eratosthenes — Finding All Primes Fast

Real-world analogy

What is it?

The Sieve of Eratosthenes is an ancient algorithm that finds all prime numbers up to a given limit N. It works by repeatedly marking the multiples of each prime as composite (not prime), starting from 2. After the sieve completes, every unmarked number is prime.

Real-world relevance

Primes are the backbone of internet security — every time you shop online or send a message, encryption algorithms use huge prime numbers to keep your data safe. The sieve is also used in hash table design, random number generators, and mathematical research. In CP, it's essential for any problem involving primes or factors.

Key points

• What Is a Sieve? — A sieve is like a filter that lets only certain things through. In our case, we start by assuming every number is prime (innocent until proven guilty!). Then we systematically remove the non-primes by crossing out multiples. What's left after all the crossing out? Only the true primes survive the sieve!
• Marking Composites — A composite number is one that can be broken into smaller factors — like 12 = 2 × 6. When we find a prime number p, we mark ALL its multiples (2p, 3p, 4p…) as composite (not prime). It's like finding one bad apple and removing its entire gang. After we finish marking, any number still marked as prime is genuinely prime.
• Finding All Primes Up to N — The sieve finds EVERY prime from 2 up to any number N you choose. Need all primes up to 1 million? The sieve handles it in a flash! You create a boolean array of size N+1, set everything to true, then start crossing out. This is way faster than checking each number individually — especially when N is large.
• The i×i Optimization — Here's a neat trick: when crossing out multiples of prime p, you can start from p×p instead of 2×p. Why? Because smaller multiples like 2×p, 3×p, etc., were already crossed out by earlier primes! For example, when handling prime 5, you start at 25 because 10 was crossed out by 2, and 15 was crossed out by 3. This makes the sieve even faster.
• Using a Bool Array — We use an array of true/false values to track which numbers are prime. Index i in the array represents the number i. Start with all values set to true (all are prime candidates). As we cross out composites, we flip their values to false. At the end, if is_prime[i] is still true, then i is a prime number. Simple and elegant!
• Counting Primes — After running the sieve, counting primes is super easy — just count how many entries are still marked true! Many CP problems ask 'how many primes are there up to N?' and the sieve answers this instantly. You can even store the primes in a separate list for quick access later.
• Smallest Prime Factor — A cool bonus: you can modify the sieve to record the smallest prime factor of every number. Instead of just marking true/false, store which prime first crossed out each number. This is incredibly useful for quickly factoring numbers later — just keep dividing by the smallest prime factor until you reach 1.
• Why Only Check Up to √N? — You only need to run the outer sieve loop up to the square root of N. If a number bigger than √N is composite, it must have a factor smaller than √N — and that factor's prime would have already crossed it out. So once you pass √N, all remaining unmarked numbers are guaranteed prime. This saves a huge amount of work!
• Sieve in Competitive Programming — The sieve is one of the most common tools in CP. Problems involving primes, divisors, or factorization almost always benefit from pre-computing a sieve. It runs in roughly O(N log log N) time, which is nearly linear — meaning it can handle N up to 10 million in well under a second. Build the sieve once, answer many queries fast!

Code example

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cout << "Find all primes up to: ";
    cin >> n;

    // Create a bool array, assume all are prime
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false; // 0 and 1 are not prime

    // Sieve: cross out multiples of each prime
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            // Start crossing from i*i (optimization!)
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    // Collect and print all primes
    vector<int> primes;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }

    cout << "Found " << primes.size() << " primes:\n";
    for (int p : primes) {
        cout << p << " ";
    }
    cout << endl;

    return 0;
}

Line-by-line walkthrough

1. 1. We include our standard library and start the main function.
2. 2. We ask the user for a number n — we'll find all primes up to this number.
3. 3. We create a vector of booleans called is_prime with n+1 slots, all set to true. Each slot represents whether that number is prime.
4. 4. We manually set is_prime[0] and is_prime[1] to false because 0 and 1 are never prime.
5. 5. The outer loop runs i from 2 up to √n (using the condition i*i <= n). For each i, we check if it's still marked prime.
6. 6. If i is prime, the inner loop crosses out all multiples of i starting from i*i. We set is_prime[j] = false for each multiple j.
7. 7. After the sieve finishes, we loop through the array and collect every number still marked true into a primes vector.
8. 8. We print how many primes were found, then print each prime separated by spaces.
9. 9. The whole process is incredibly fast — even for n = 10,000,000, it finishes in well under a second!

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 30;
    vector<bool> is_prime(n + 1, true);

    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = 2 * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    // Print all primes
    for (int i = 0; i <= n; i++) {
        if (is_prime[i]) cout << i << " ";
    }
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Sieve of Eratosthenes Visualized (YouTube)
• Sieve of Eratosthenes — CP-Algorithms (CP-Algorithms)
• Prime Sieve Problems on Codeforces (Codeforces)