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.

Practice

1. What is the main purpose of the Sieve of Eratosthenes algorithm?

easy

A. To sort an array of numbers

B. To find all prime numbers up to a given limit

C. To find the greatest common divisor of two numbers

D. To reverse a string

Solution

1. Step 1: Understand the algorithm's goal

   The Sieve of Eratosthenes is designed to identify prime numbers efficiently.

2. Step 2: Recognize the output

   It marks multiples of primes as non-prime to find all primes up to a limit.

3. Final Answer:

   To find all prime numbers up to a given limit -> Option B

4. Quick Check:

   Prime finding = B [OK]

Hint: Sieve marks multiples to find primes fast [OK]

Common Mistakes:

• Confusing prime finding with sorting
• Thinking it finds divisors or reverses strings
• Assuming it works for negative numbers

2. Which of the following is the correct way to initialize the sieve array in C for finding primes up to n?

easy

A. int sieve[n+1]; for(int i=0; i<=n; i++) sieve[i] = 1;

B. int sieve[n]; for(int i=1; i

C. int sieve[n+1]; for(int i=0; i<=n; i++) sieve[i] = 0; sieve[0] = sieve[1] = 1;

D. int sieve[n+1]; for(int i=0; i<=n; i++) sieve[i] = i;

Solution

1. Step 1: Understand sieve initialization

   The sieve array uses 1 to mark potential primes initially.

2. Step 2: Check array size and initialization

   Array size should be n+1 to include number n, and all set to 1 (true) initially.

3. Final Answer:

   int sieve[n+1]; for(int i=0; i<=n; i++) sieve[i] = 1; -> Option A

4. Quick Check:

   Initialize all to 1 for primes [OK]

Hint: Initialize all to 1 (true) for prime candidates [OK]

Common Mistakes:

• Using size n instead of n+1
• Initializing with zeros instead of ones
• Marking 0 and 1 as prime initially

3. What will be the output of the following C code snippet using Sieve of Eratosthenes to find primes up to 10?

int n = 10;
int sieve[11];
for(int i=0; i<=n; i++) sieve[i] = 1;
sieve[0] = sieve[1] = 0;
for(int i=2; i*i<=n; i++) {
  if(sieve[i]) {
    for(int j=i*i; j<=n; j+=i) sieve[j] = 0;
  }
}
for(int i=2; i<=n; i++) {
  if(sieve[i]) printf("%d ", i);
}

medium

A. 2 3 4 5 7

B. 1 2 3 5 7

C. 2 3 5 7 9

D. 2 3 5 7

Solution

1. Step 1: Initialize sieve and mark 0,1 as non-prime

   Array sieve marks 0 and 1 as 0 (not prime), others as 1 (prime candidate).

2. Step 2: Mark multiples of primes as non-prime

   For i=2, mark 4,6,8,10 as 0; for i=3, mark 9 as 0.

3. Step 3: Print all indices with sieve[i] = 1

   Primes are 2, 3, 5, 7 only.

4. Final Answer:

   2 3 5 7 -> Option D

5. Quick Check:

   Primes up to 10 = 2 3 5 7 [OK]

Hint: Mark multiples starting from i*i to avoid repeats [OK]

Common Mistakes:

• Printing 1 as prime
• Including non-primes like 4 or 9
• Starting marking multiples from i instead of i*i

4. Identify the error in this Sieve of Eratosthenes code snippet and choose the correct fix:

int n = 20;
int sieve[21];
for(int i=0; i<=n; i++) sieve[i] = 1;
sieve[0] = sieve[1] = 0;
for(int i=2; i<=n; i++) {
  if(sieve[i]) {
    for(int j=2*i; j<=n; j+=i) sieve[j] = 0;
  }
}

medium

A. Remove sieve[0] and sieve[1] assignments

B. Initialize sieve array with zeros instead of ones

C. Change outer loop condition to i*i <= n

D. Start inner loop from j = i instead of 2*i

Solution

1. Step 1: Analyze outer loop condition

   Outer loop runs from 2 to n, but it should run only up to sqrt(n) for efficiency.

2. Step 2: Understand inner loop start

   Inner loop correctly starts from 2*i, but starting from i*i is more optimal.

3. Step 3: Correct the outer loop condition

   Change outer loop to for(i=2; i*i<=n; i++) to avoid unnecessary iterations.

4. Final Answer:

   Change outer loop condition to i*i <= n -> Option C

5. Quick Check:

   Outer loop till sqrt(n) improves sieve [OK]

Hint: Outer loop runs only to sqrt(n) for marking multiples [OK]

Common Mistakes:

• Running outer loop till n wastes time
• Starting inner loop from 2*i instead of i*i (less efficient)
• Not marking 0 and 1 as non-prime

5. You want to find all prime numbers up to 50 using the Sieve of Eratosthenes. After running the sieve, how many numbers will remain marked as prime?

hard

A. 15

B. 16

C. 14

D. 13

Solution

1. Step 1: List primes up to 50

   Primes are: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 (total 15).

2. Step 2: Count primes carefully

   Counting again: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 = 15 primes.

3. Step 3: Check if 1 is counted

   1 is not prime, so total primes = 15.

4. Final Answer:

   15 -> Option A

5. Quick Check:

   Count primes up to 50 = 15 [OK]

Hint: Count known primes or use sieve output count [OK]

Common Mistakes:

• Including 1 as prime
• Miscounting primes between 40 and 50
• Forgetting to exclude non-primes