Sieve of Eratosthenes: Find All Primes up to N Fast (C++)

Checking whether one number is prime is easy: try dividing it by everything up to its square root. But when a problem needs to know about every number up to 10⁶ or 10⁷, repeating that check for each number is too slow. The Sieve of Eratosthenes, which is more than two thousand years old, finds all of them at once.

The idea

Write down all numbers from 2 to n, and assume they are all prime. Then:

1. Take the smallest number that is still marked prime. Call it p. It really is prime, because no smaller number divided it.
2. Cross out every multiple of p: they have p as a factor, so they are composite.
3. Move on to the next number that is still marked and repeat.

Whatever survives is prime.

Example with n = 30

• p = 2: cross out 4, 6, 8, …, 30.
• p = 3: cross out 9, 15, 21, 27 (12, 18, 24 and 30 were already gone).
• p = 5: cross out 25 (30 was already gone).
• p = 7: 7 × 7 = 49 > 30, so we can stop.

The survivors are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29: ten primes.

Two small optimisations that matter

Start crossing at p × p. Any smaller multiple k × p with k < p has a prime factor smaller than p, so it was already crossed out earlier. For p = 5 above, 10, 15 and 20 were already gone, so we start at 25.

Stop the outer loop at √n. Once p × p > n, there is nothing left to cross out. Every composite number up to n has a prime factor at most √n, so it has already been handled.

Code (C++)

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

int main() {
    int n;
    cin >> n;

    // is_prime[x] is true if x is prime, for 0 <= x <= n
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = false;
    if (n >= 1) is_prime[1] = false;

    for (long long p = 2; p * p <= n; p++) {
        if (!is_prime[p]) continue;
        for (long long m = p * p; m <= n; m += p)
            is_prime[m] = false;
    }

    int count = 0;
    for (int x = 2; x <= n; x++)
        if (is_prime[x]) count++;
    cout << count << '\n';
    return 0;
}

The program prints how many primes there are up to n. For n = 10⁶ it prints 78 498, and for n = 10⁷ it prints 664 579. Once is_prime is built, each “is x prime?” question is a single array lookup.

Complexity

For each prime p, the inner loop does about n / p steps. Summing n/2 + n/3 + n/5 + … over primes gives O(n log log n), which is almost linear in practice. Memory is O(n). vector<bool> stores one bit per entry, so a sieve up to 10⁷ needs only about 1.25 MB.

Common mistakes

• Forgetting that 0 and 1 are not prime.
• Writing p * p <= n with int when n is close to the int limit. The product can overflow, so use long long for p, as in the code above.
• Re-running the sieve for every test case. Build it once, up to the largest value you will need.

A useful variation: smallest prime factor

Instead of a true/false flag, store for every number its smallest prime factor. Then you can factorise any number up to n in O(log n) by repeatedly dividing by its smallest prime factor. This is the standard way to factorise many numbers quickly.

Practice problems

• Codeforces 26A – Almost Prime: count numbers up to n with exactly two distinct prime divisors.
• Codeforces 230B – T-primes: numbers with exactly three divisors are squares of primes. Sieve up to 10⁶ and check.

For a gentler number theory warm-up, see Lucky Division (122A).