L6. Sieve of Eratosthenes | Maths Playlist

A comprehensive study note on the Sieve of Eratosthenes algorithm, transitioning from naive prime-checking approaches to an ultra-efficient precomputation strategy for generating all prime numbers up to $N$.

1. Why Do We Need This? (Problem Statement & Status Quo)

The fundamental problem tackled in this chapter is straightforward: Given a number $N$, print all prime numbers up to $N$.

• Example: If $N = 10$, the expected output is 2, 3, 5, 7. There are four prime numbers up to $10$.
• The Naive Approach:
  • Iterate from $i = 2$ up to $N$.
  • For each integer $i$, invoke a helper function to check if it is prime (which takes $O(\sqrt{i})$ time).
• Time Complexity of Naive Approach: $O(N \cdot \sqrt{N})$
• Space Complexity: $O(1)$

The Bottleneck in Production

Imagine $N = 10^5$. Running a loop up to $10^5$ and executing a square-root prime check for each integer results in an extraordinarily expensive operation ($10^5 \times \sqrt{10^5}$ operations). For $N = 10^6$, the execution time becomes unacceptably sluggish.

To solve this, we need to eliminate the per-number prime check and achieve $O(1)$ constant-time lookups for any number's primality status.

2. Core Mental Model: The Elimination Paradigm

Instead of testing whether every individual number is prime from scratch, the Sieve of Eratosthenes flips the perspective: If a number is prime, all of its multiples are guaranteed to be composite (non-prime).

Real-Life Analogy: The Strike-Off Board

Imagine sitting in a classroom with a numbered grid from $2$ to $30$ written on a blackboard.

• You walk to the first number ($2$), realize it's circled (prime), and immediately walk down the rows crossing out every second number ($4, 6, 8, 10, \dots$) because they are multiples of $2$.
• You move to the next uncrossed number ($3$), circle it, and cross out every third number ($6, 9, 12, 15, \dots$).
• By systematically walking through and eliminating multiples, you never have to "test" remaining numbers; whatever survives uncrossed at the end is strictly a prime.

3. Step-by-Step Walkthrough ($N = 30$)

Let us trace how the algorithm processes up to $N = 30$ using an array of size $31$ (omitting indices $0$ and $1$).

1. Initialization: Declare a prime array of size $31$. Initialize every index from $2$ to $30$ with 1 (representing "tentatively prime").
2. Processing $i = 2$:
   • $2$ is marked as prime (1).
   • Strike off all multiples of $2$ by setting them to 0: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 become 0.
3. Processing $i = 3$:
   • $3$ is still 1 (prime).
   • Strike off its multiples starting from $6$: 6, 9, 12, 15, 18, 21, 24, 27, 30 become 0.
4. Processing $i = 4$:
   • Index $4$ is already 0 (marked earlier by $2$). Since it is not prime, we skip striking off its multiples (because all multiples of $4$ are already multiples of $2$).
5. Processing $i = 5$:
   • $5$ is 1 (prime). Strike off its multiples: 10, 15, 20, 25, 30. ($25$ is newly marked 0).

Final State of Primes up to $30$

After evaluating up to $\sqrt{30}$, the indices remaining marked as 1 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

4. Naive Sieve Code vs. Optimized Sieve Code

Naive Implementation (Unoptimized Multiples Loop)

void simpleSieve(int n) {
    vector<int> prime(n + 1, 1);
    prime[0] = prime[1] = 0;

    for (int i = 2; i <= n; i++) {
        if (prime[i] == 1) {
            // Starts marking from 2 * i
            for (int j = 2 * i; j <= n; j += i) {
                prime[j] = 0;
            }
        }
    }
}

Critical Inefficiencies in Naive Code

• When $i = 5$, the inner loop starts at 5 * 2 = 10, then 5 * 3 = 15, then 5 * 4 = 20.
• However, 10 was already marked by $2$ (2 * 5), and 20 was already marked by $2$ (2 * 10). Redundantly visiting already-crossed numbers wastes CPU cycles.

5. Optimizing the Sieve (Two Crucial Enhancements)

To make the algorithm production-ready, we introduce two mathematical optimizations:

Optimization 1: Start Inner Loop from $i^2$

Instead of starting multiples at $2 \times i$, we can start directly at $i \times i$.

• Why? Any multiple smaller than $i^2$ (like $2 \times i, 3 \times i, \dots, (i-1) \times i$) would have already been marked by a smaller prime factor.
• Example for $5$: $5 \times 2$ was handled by $2$, $5 \times 3$ was handled by $3$. The first fresh multiple that only gets marked by $5$ is $5 \times 5 = 25$.

Optimization 2: Outer Loop Boundary at $\sqrt{N}$

Instead of running the outer loop up to $N$, we only need to run it up to $\sqrt{N}$ (or check $i \times i \le N$).

• Why? If $N = 30$, $\sqrt{30} \approx 5.47$. Once $i = 7$, $7 \times 7 = 49$, which exceeds $30$. Thus, numbers greater than $\sqrt{N}$ cannot have unvisited composite multiples within range $N$.

6. Complete Optimized Code Implementation

Here is the clean, optimized implementation of the Sieve of Eratosthenes across popular languages:

C++ Implementation

#include <iostream>
#include <vector>

using namespace std;

void sieveOfEratosthenes(int n) {
    // Step 1: Create a prime array of size n + 1, initialized to 1 (true)
    vector<int> prime(n + 1, 1);
    prime[0] = prime[1] = 0;

    // Step 2: Loop from 2 up to sqrt(n)
    for (int i = 2; i * i <= n; i++) {
        if (prime[i] == 1) {
            // Step 3: Mark all multiples of i starting from i * i
            for (int j = i * i; j <= n; j += i) {
                prime[j] = 0;
            }
        }
    }

    // Step 4: Print all prime numbers
    cout << "Primes up to " << n << ": ";
    for (int i = 2; i <= n; i++) {
        if (prime[i] == 1) {
            cout << i << " ";
        }
    }
    cout << endl;
}

int main() {
    int n = 30;
    sieveOfEratosthenes(n);
    return 0;
}

Python Implementation

def sieve_of_eratosthenes(n):
    prime = [1] * (n + 1)
    prime[0] = prime[1] = 0
    
    i = 2
    while i * i <= n:
        if prime[i] == 1:
            for j in range(i * i, n + 1, i):
                prime[j] = 0
        i += 1
        
    primes = [i for i in range(2, n + 1) if prime[i] == 1]
    return primes

print(sieve_of_eratosthenes(30))

7. Complexity Analysis

8. Summary and Key Takeaways

• Elimination over Testing: The Sieve of Eratosthenes bypasses expensive trial division by systematically striking out multiples of known primes.
• Constant-Time Black Box: Through one-time precomputation, primality queries for any number up to $N$ are reduced from $O(\sqrt{N})$ down to $O(1)$.
• $i \times i$ Optimization: Inner loops for any prime $i$ do not need to start at $2 \times i$; they can safely begin at $i^2$ because smaller multiples are already eliminated by prior primes.
• $\sqrt{N}$ Outer Loop Boundary: The outer loop execution terminates at $\sqrt{N}$ because higher prime factors have already exhausted their composite footprints within $N$.
• Sub-Linear Growth: The time complexity of $O(N \log(\log N))$ makes this algorithm exceptionally fast even for large inputs such as $N = 10^7$.
• Space-Time Tradeoff: We trade extra memory ($O(N)$ array storage) for massive speedups in computational throughput.