Sieve of Eratosthenes: Finding Primes to N

The Need for a Better Approach: From Single Queries to Pre-computation

Imagine a problem where you're given up to $10^6$ queries, and for each query, you need to check if a number (up to $10^6$) is prime. Using the O(sqrt(n)) method from our previous lesson would result in roughly $10^6\times \sqrt{10^6}=10^6\times 10^3=10^9$ operations in the worst case. This is far too slow for a typical time limit of one second (which allows for about $10^8$ operations).

This problem structure—many queries on a fixed range of data—is a strong signal that pre-computation is the right strategy. The idea is to do some initial work to build a data structure that can then answer each query very quickly. The Sieve of Eratosthenes is a perfect example of this.

To see this scenario explained in the context of a competitive programming problem, watch the following segment from the CodeBeyond channel.

The Sieve of Eratosthenes: The Core Idea

The Sieve of Eratosthenes works on a simple, elegant principle. Instead of testing each number for primality, we take a different view: if a number is composite, it must be a multiple of some smaller prime number.

The algorithm proceeds as follows:

1. Create a boolean array, let's call it is_prime, of size N+1. Initialize all entries from 2 to N as true, assuming every number is a potential prime. Mark 0 and 1 as false.
2. Start with the first prime number, p = 2.
3. Mark all multiples of p (i.e., 2*p, 3*p, 4*p, ...) up to N as false in the is_prime array, because they are clearly not prime.
4. Find the next number greater than p that is still marked true. This number is the next prime. Let this be our new p.
5. Repeat steps 3 and 4 until you have processed all necessary primes.

The numbers that remain marked true at the end are all the prime numbers up to N. This process is like sifting out the composite numbers, leaving only the primes behind.

For a dynamic walkthrough of this process, the same video provides an excellent dry run.

From Naive Sieve to Optimized Implementation

A direct translation of the idea above would work, but we can make two crucial optimizations that are standard practice in competitive programming. For a concise explanation and C++ implementation, we'll turn to the cp-algorithms website, a vital resource for competitive programmers.

Let's break down that first optimization:

• Optimization 1: Start marking from i*i
  When we are processing a prime i, why do we start marking its multiples from i*i instead of 2*i? Consider a multiple like k*i where k < i. This number k*i must have a prime factor that is less than or equal to k. Since k < i, this prime factor is also less than i. This means the number k*i would have already been marked as composite when we processed that smaller prime factor. For example, when i=5, we don't need to mark 2*5=10 (marked by 2), 3*5=15 (marked by 3), or 4*5=20 (marked by 2). The first multiple we need to consider is 5*5=25.

This leads us to the second major optimization.

• Optimization 2: Outer loop only needs to run up to sqrt(N)
  This follows directly from the first optimization. Since the inner loop starts marking at i*i, if i is greater than sqrt(N), then i*i will be greater than N. The inner loop would do no work at all. Therefore, we only need to run the outer loop for primes i up to sqrt(N).

Putting these together gives us the standard, efficient implementation of the Sieve:

void 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;
        }
    }
    // Now is_prime[k] is true if k is prime, false otherwise.
}

Complexity and Practical Considerations

• Time Complexity: The optimized Sieve of Eratosthenes runs in O(N log log N) time. The proof is based on the prime harmonic series, but for competitive programming purposes, you can consider this to be very close to linear, i.e., almost O(N), because log log N grows extremely slowly.

• Space Complexity: The algorithm requires a boolean array of size N+1, so the space complexity is O(N).

As a C++ programmer aiming for high performance, there are a couple more practical details worth knowing.

1. vector<bool> vs. vector<char>: C++'s vector<bool> is a specialized template that packs booleans into bits to save space (using 8x less memory than vector<char>). While this is memory-efficient, accessing individual bits can be slower than accessing full bytes. For the Sieve, however, where memory access patterns are the bottleneck, vector<bool> is often faster.

2. Array Declaration Limits: In C++, arrays declared inside a function (local scope, on the stack) have a strict size limit, typically around a few megabytes. An array like bool is_prime[10000000] would cause a stack overflow. To use large arrays, you must declare them globally (outside of any function), where the memory is allocated differently and the limit is much higher.

The following resources elaborate on these points.

Summary and Next Steps

You've now added a powerful pre-computation algorithm to your arsenal. Here are the key takeaways:

• The Sieve of Eratosthenes is used to find all primes up to N efficiently, which is ideal for problems with multiple queries.
• The core idea is to iteratively mark the multiples of prime numbers as composite.
• Key optimizations are essential: the outer loop runs up to sqrt(N), and the inner marking loop starts from i*i.
• The time complexity is O(N log log N), which is very fast in practice.
• The space complexity is O(N).
• For C++ implementation, be mindful of practical details like using vector<bool> and declaring large arrays globally.

In our previous lesson, we learned to test a single number for primality. Today, we learned to find all primes up to N. In the next lesson, we will combine these ideas to tackle another fundamental problem: finding the prime factorization of a number. The Sieve can even be adapted to make this process faster, a connection we will explore soon.