Sieve of Eratosthenes Find All Primes in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sieve for n=10

What is the output of the following C# code that uses the Sieve of Eratosthenes to find all primes up to 10?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int n = 10;
        bool[] isPrime = new bool[n + 1];
        for (int i = 2; i <= n; i++) isPrime[i] = true;

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

        List<int> primes = new List<int>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) primes.Add(i);
        }

        Console.WriteLine(string.Join(", ", primes));
    }
}

A [1, 2, 3, 5, 7]

B [2, 3, 4, 5, 7]

C [2, 3, 5, 6, 7]

D [2, 3, 5, 7]

💡 Hint

Remember that primes are numbers greater than 1 with no divisors other than 1 and themselves.

The Sieve marks multiples of each prime as false. For n=10, primes are 2, 3, 5, and 7 only.

❓ Predict Output

intermediate

Number of primes up to 20

How many prime numbers does the following code find up to 20?

DSA C#

int n = 20;
bool[] prime = new bool[n + 1];
for (int i = 2; i <= n; i++) prime[i] = true;
for (int i = 2; i * i <= n; i++) {
    if (prime[i]) {
        for (int j = i * i; j <= n; j += i) prime[j] = false;
    }
}
int count = 0;
for (int i = 2; i <= n; i++) {
    if (prime[i]) count++;
}
Console.WriteLine(count);

A 8

B 9

C 7

D 10

💡 Hint

List primes up to 20: 2,3,5,7,11,13,17,19

There are exactly 8 primes up to 20: 2,3,5,7,11,13,17,19.

🔧 Debug

advanced

Identify the error in Sieve implementation

What error does the following code produce when run?

DSA C#

int n = 15;
bool[] prime = new bool[n];
for (int i = 2; i <= n; i++) prime[i] = true;
for (int i = 2; i * i <= n; i++) {
    if (prime[i]) {
        for (int j = i * i; j <= n; j += i) prime[j] = false;
    }
}
int count = 0;
for (int i = 2; i <= n; i++) {
    if (prime[i]) count++;
}
Console.WriteLine(count);

A NullReferenceException

B IndexOutOfRangeException

C No error, outputs 6

D SyntaxError

💡 Hint

Check array size and indexing carefully.

The array size is n (15), but code accesses prime[15], which is out of bounds since valid indices are 0 to 14.

🧠 Conceptual

advanced

Why start marking multiples from i*i?

In the Sieve of Eratosthenes, why do we start marking multiples of a prime number i from i*i instead of 2*i?

A Because all smaller multiples of i were already marked by smaller primes

B Because starting from 2*i causes runtime errors

C Because 2*i might not be a multiple of i

D Because i*i is the smallest prime number

💡 Hint

Think about when smaller multiples get marked.

Multiples less than i*i are already marked by smaller primes, so starting at i*i avoids redundant work.

❓ Predict Output

expert

Output of Sieve with n=30 and printing primes in ascending order

What is the output of this C# code that finds primes up to 30 using the Sieve of Eratosthenes and prints them in ascending order?

DSA C#

int n = 30;
bool[] prime = new bool[n + 1];
for (int i = 2; i <= n; i++) prime[i] = true;
for (int i = 2; i * i <= n; i++) {
    if (prime[i]) {
        for (int j = i * i; j <= n; j += i) prime[j] = false;
    }
}
for (int i = 2; i <= n; i++) {
    if (prime[i]) Console.Write(i + " ");
}

A 2 3 5 7 11 13 17 19 23 27 29

B 2 3 5 7 9 11 13 17 19 23 29

C 2 3 5 7 11 13 17 19 23 29

D 2 3 5 7 11 13 17 19 23 25 29

💡 Hint

Remember that primes do not include composite numbers like 9, 25, or 27.

The Sieve correctly marks all non-primes false. The primes up to 30 are 2,3,5,7,11,13,17,19,23,29.

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