Sieve of Eratosthenes Find All Primes in DSA C#

Mental Model

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

Analogy: Imagine a list of people standing in a line. Starting from the second person, you ask every second person to step out, then every third person, and so on, until only the prime-numbered people remain.

Index:  0  1  2  3  4  5  6  7  8  9  10
Value: [F][F][T][T][T][T][T][T][T][T][T]
Legend: T = possibly prime, F = not prime

Dry Run Walkthrough

Input: Find all primes up to 10

Goal: Identify all prime numbers from 2 to 10 using the sieve method

Step 1: Start with list marking 0 and 1 as not prime, others as prime candidates

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 numbers, so mark them false

Step 2: Mark multiples of 2 (except 2) as not prime: 4, 6, 8, 10

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: Move to next prime candidate 3, mark multiples of 3 (except 3) as not prime: 6, 9

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 prime candidate is 4 but it is marked false, skip to 5

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: 4 is not prime, so skip marking multiples

Step 5: Mark multiples of 5 (except 5) as not prime: 10 (already marked)

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 5 are not prime, but 10 already marked

Step 6: Stop because next prime candidate 6 squared (36) is greater than 10

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: No need to check beyond square root of limit

Result:

Primes are indices with True: 2 -> 3 -> 5 -> 7 -> null

Annotated Code

DSA C#

using System;

class SieveOfEratosthenes
{
    public static void FindPrimes(int n)
    {
        bool[] isPrime = new bool[n + 1];
        for (int i = 2; i <= n; i++)
            isPrime[i] = true; // assume all are prime initially

        for (int i = 2; i * i <= n; i++)
        {
            if (isPrime[i])
            {
                for (int j = i * i; j <= n; j += i)
                    isPrime[j] = false; // mark multiples as not prime
            }
        }

        for (int i = 2; i <= n; i++)
        {
            if (isPrime[i])
                Console.Write(i + " -> ");
        }
        Console.WriteLine("null");
    }

    static void Main()
    {
        FindPrimes(10);
    }
}

for (int i = 2; i <= n; i++) isPrime[i] = true; // assume all are prime initially

initialize all numbers from 2 to n as potential primes

for (int i = 2; i * i <= n; i++)

iterate only up to square root of n to optimize

if (isPrime[i])

process only numbers still marked prime

for (int j = i * i; j <= n; j += i) isPrime[j] = false; // mark multiples as not prime

mark all multiples of i starting from i squared as not prime

for (int i = 2; i <= n; i++) if (isPrime[i]) Console.Write(i + " -> ");

print all numbers still marked prime

Output

2 -> 3 -> 5 -> 7 -> null

Complexity Analysis

Time: O(n log log n) because the sieve marks multiples efficiently up to n

Space: O(n) because it uses a boolean array of size n+1 to track primes

vs Alternative: Compared to checking each number individually for primality (O(n√n)), sieve is much faster for large n

Edge Cases

n less than 2

No primes are printed because primes start from 2

DSA C#

for (int i = 2; i <= n; i++)
    isPrime[i] = true;

n equals 2

Only 2 is printed as prime

DSA C#

for (int i = 2; i <= n; i++)
    if (isPrime[i])
        Console.Write(i + " -> ");

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 systematically to avoid repeated checks.

Common Mistakes

Mistake: Starting inner loop from i*2 instead of i*i, causing redundant marking
Fix: Start marking multiples from i*i because smaller multiples were already marked by smaller primes

Mistake: Iterating i up to n instead of up to sqrt(n), causing unnecessary work
Fix: Stop outer loop at i*i <= n to optimize performance

Summary

Finds all prime numbers up to a given number by marking multiples as not prime.

Use when you need to list primes efficiently up to a limit.

The key insight is to start marking multiples from the square of each prime candidate.

Practice

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

easy

A. To sort an array of numbers

B. To find the greatest common divisor of two numbers

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

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 C

4. Quick Check:

   Sieve of Eratosthenes = Find primes [OK]

Hint: Remember: Sieve filters out non-primes to list primes [OK]

Common Mistakes:

• Confusing it with sorting algorithms
• Thinking it finds factors instead of primes
• Assuming it works on strings

2. Which of the following C# code snippets correctly initializes a boolean array for the sieve to find primes up to n?

easy

A. bool[] isPrime = new bool[n + 1]; for(int i = 0; i <= n; i++) isPrime[i] = false;

B. bool[] isPrime = new bool[n + 1]; for(int i = 2; i <= n; i++) isPrime[i] = true;

C. bool[] isPrime = new bool[n]; for(int i = 0; i < n; i++) isPrime[i] = false;

D. bool[] isPrime = new bool[n]; for(int i = 2; i < n; i++) isPrime[i] = true;

Solution

1. Step 1: Check array size and initialization

   The array must be of size n+1 to include index n, and primes start from 2.

2. Step 2: Verify initialization values

   All entries from 2 to n should be set to true initially to mark potential primes.

3. Final Answer:

   bool[] isPrime = new bool[n + 1]; for(int i = 2; i <= n; i++) isPrime[i] = true; -> Option B

4. Quick Check:

   Array size n+1 and true from 2 to n [OK]

Hint: Array size n+1 and true from 2 to n for primes [OK]

Common Mistakes:

• Using array size n instead of n+1
• Initializing all values to false
• Starting initialization from 0 or 1

3. What will be the output list of primes when running the Sieve of Eratosthenes for n = 10?

medium

A. [2, 3, 5, 7, 9]

B. [1, 2, 3, 5, 7]

C. [2, 3, 4, 5, 7]

D. [2, 3, 5, 7]

Solution

1. Step 1: Identify primes up to 10

   Primes are numbers greater than 1 with no divisors other than 1 and themselves: 2, 3, 5, 7.

2. Step 2: Exclude non-primes

   Numbers 1, 4, 6, 8, 9, 10 are not prime.

3. Final Answer:

   [2, 3, 5, 7] -> Option D

4. Quick Check:

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

Hint: Remember primes > 1 and exclude multiples [OK]

Common Mistakes:

• Including 1 as prime
• Including even numbers > 2
• Including non-prime odd numbers like 9

4. Consider this code snippet for the sieve:

for (int i = 2; i * i <= n; i++) {
  if (isPrime[i]) {
    for (int j = i * 2; j <= n; j += i) {
      isPrime[j] = false;
    }
  }
}

Which of the following improves the efficiency of this code?

medium

A. The inner loop should start from i * i, not i * 2

B. The outer loop condition should be i <= n, not i * i <= n

C. The inner loop increments should be j += 1, not j += i

D. The isPrime array should be initialized with false, not true

Solution

1. Step 1: Understand sieve optimization

   Marking multiples starts from i squared because smaller multiples were marked by smaller primes.

2. Step 2: Identify suboptimal start of inner loop

   Starting from i*2 repeats marking multiples already handled; correct start is i*i.

3. Final Answer:

   The inner loop should start from i * i, not i * 2 -> Option A

4. Quick Check:

   Start inner loop at i*i for efficiency [OK]

Hint: Start marking multiples from i squared, not double i [OK]

Common Mistakes:

• Starting inner loop at i*2 causing redundant work
• Changing outer loop condition incorrectly
• Incorrect increment steps in inner loop

5. You want to find all prime numbers up to n = 30 using the Sieve of Eratosthenes. After running the sieve, which of the following lists correctly shows the primes and their count?

hard

A. Primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29], Count: 10

B. Primes: [2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 29], Count: 11

C. Primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29], Count: 11

D. Primes: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29], Count: 11

Solution

1. Step 1: List primes up to 30

   Primes are numbers >1 with no divisors except 1 and themselves: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

2. Step 2: Count and verify correctness

   Count is 10; numbers like 9, 25, and 1 are not prime and should be excluded.

3. Final Answer:

   Primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29], Count: 10 -> Option A

4. Quick Check:

   Correct primes and count up to 30 [OK]

Hint: Exclude 1 and non-primes like 9, 25; count primes carefully [OK]

Common Mistakes:

• Including 1 as prime
• Including composite numbers like 9 or 25
• Miscounting the total primes