Sieve of Eratosthenes Find All Primes in DSA C

Mental Model

We mark multiples of each prime number as not prime, so only primes remain unmarked.

Analogy: Imagine a list of numbers like a row of houses. You paint all houses that are multiples of a number red, leaving only prime-numbered houses unpainted.

Index:  0  1  2  3  4  5  6  7  8  9  10
Value: F  F  T  T  T  T  T  T  T  T   T
(F = false, T = true, initially all true except 0 and 1)

Dry Run Walkthrough

Input: Find all primes up to 10

Goal: Mark all non-prime numbers false, leaving only primes true

Step 1: Initialize array with true for 2 to 10, false for 0 and 1

Index:  0  1  2  3  4  5  6  7  8  9  10
Value: F  F  T  T  T  T  T  T  T  T   T

Why: 0 and 1 are not prime, others start as possibly prime

Step 2: Start with p=2, mark multiples of 2 (4,6,8,10) as false

Index:  0  1  2  3  4  5  6  7  8  9  10
Value: F  F  T  T  F  T  F  T  F  T   F

Why: Multiples of 2 cannot be prime

Step 3: Next p=3, mark multiples of 3 (9) as false

Index:  0  1  2  3  4  5  6  7  8  9  10
Value: F  F  T  T  F  T  F  T  F  F   F

Why: Multiples of 3 cannot be prime

Step 4: Next p=4 is false, skip to p=5 which is true, no multiples ≤10 to mark

Index:  0  1  2  3  4  5  6  7  8  9  10
Value: F  F  T  T  F  T  F  T  F  F   F

Why: 5 is prime, no multiples within range

Step 5: Next p=6 is false, skip to p=7 which is true, no multiples ≤10 to mark

Index:  0  1  2  3  4  5  6  7  8  9  10
Value: F  F  T  T  F  T  F  T  F  F   F

Why: 7 is prime, no multiples within range

Result:

Primes are indices with true: 2, 3, 5, 7

Annotated Code

DSA C

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

void sieve_of_eratosthenes(int n) {
    bool prime[n+1];
    for (int i = 0; i <= n; i++) {
        prime[i] = true; // assume all are prime initially
    }
    prime[0] = false; // 0 is not prime
    prime[1] = false; // 1 is not prime

    int limit = (int)sqrt(n);
    for (int p = 2; p <= limit; p++) {
        if (prime[p]) {
            // mark multiples of p as not prime
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false; // mark multiple as not prime
            }
        }
    }

    // print all primes
    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");
}

int main() {
    int n = 10;
    sieve_of_eratosthenes(n);
    return 0;
}

prime[i] = true; // assume all are prime initially

initialize all numbers as possibly prime

prime[0] = false; // 0 is not prime prime[1] = false; // 1 is not prime

mark 0 and 1 as not prime explicitly

for (int p = 2; p <= limit; p++) { if (prime[p]) {

iterate from 2 to sqrt(n), only for numbers still marked prime

for (int i = p * p; i <= n; i += p) { prime[i] = false; }

mark all multiples of p starting from p^2 as not prime

for (int i = 2; i <= n; i++) { if (prime[i]) { printf("%d ", i); } }

print all numbers still marked prime

Output

2 3 5 7 

Complexity Analysis

Time: O(n log log n) because we mark multiples of primes up to sqrt(n)

Space: O(n) because we store a boolean array for all numbers up to n

vs Alternative: Better than checking each number's divisibility individually (O(n sqrt n)) because it avoids repeated work by marking multiples once

Edge Cases

n = 0 or 1

No primes printed because 0 and 1 are not prime

DSA C

prime[0] = false; prime[1] = false;

n = 2

Only 2 is printed as prime

DSA C

for (int i = 2; i <= n; i++) { if (prime[i]) { printf(...) } }

n is a perfect square

Algorithm correctly marks multiples up to sqrt(n)

DSA C

int limit = (int)sqrt(n);

When to Use This Pattern

When asked to find all prime numbers up to a limit efficiently, use the Sieve of Eratosthenes because it marks multiples once and quickly filters primes.

Common Mistakes

Mistake: Starting to mark multiples from p*2 instead of p*p
Fix: Start marking from p*p because smaller multiples were already marked by smaller primes

Mistake: Not marking 0 and 1 as non-prime initially
Fix: Explicitly set prime[0] and prime[1] to false before starting

Summary

It finds all prime numbers up to a given number by marking multiples of primes as not prime.

Use it when you need a fast way to list primes up to a limit.

The key insight is to start marking multiples from the square of each prime to avoid redundant work.