Sieve of Eratosthenes Find All Primes in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a boolean array to mark primes up to n.

DSA C#

bool[] isPrime = new bool[[1]];

Drag options to blanks, or click blank then click option'

An + 1

Bn - 1

Cn

Dn * 2

Attempts:

3 left

💡 Hint

Common Mistakes

Using size n misses the number n itself.

Using n - 1 causes index out of range for n.

We need an array from 0 to n inclusive, so size is n + 1.

2fill in blank

medium

Complete the code to initialize all numbers as prime except 0 and 1.

DSA C#

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

Drag options to blanks, or click blank then click option'

An - 1

Bn

Cn * 2

Dn + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Looping only to n misses initializing the last number.

Looping to n - 1 misses numbers near n.

We initialize primes up to n inclusive, so loop until n + 1.

3fill in blank

hard

Fix the error in the loop condition to stop at the square root of n.

DSA C#

for (int i = 2; i <= [1]; i++)

Drag options to blanks, or click blank then click option'

An

Bn / 2

C(int)Math.Sqrt(n)

Dn - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Looping to n is inefficient.

Looping to n / 2 is more than needed.

We only need to check primes up to the square root of n.

4fill in blank

hard

Fill both blanks to mark multiples of i as not prime starting from i*i.

DSA C#

for (int j = i * i; j < [1]; j += [2]) isPrime[j] = false;

Drag options to blanks, or click blank then click option'

An + 1

Bi

Cn

Di + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from i instead of i*i marks wrong numbers.

Using wrong step size skips some multiples.

We mark multiples from i*i up to n inclusive, stepping by i.

5fill in blank

hard

Fill all three blanks to collect all primes into a list.

DSA C#

List<int> primes = new List<int>();
for (int k = 2; k < [1]; k++) {
    if (isPrime[[2]]) {
        primes.[3](k);
    }
}

Drag options to blanks, or click blank then click option'

An + 1

Bk

CAdd

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong loop limit misses last prime.

Using wrong index inside isPrime causes errors.

Using wrong method name instead of Add.

Loop through 2 to n inclusive, check isPrime[k], and add k to primes list.

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