Why Sieve of Eratosthenes Find All Primes in DSA C#?

The Big Idea

What if you could find all primes up to a million without checking each number one by one?

The Scenario

Imagine you want to find all prime numbers up to 100 by checking each number one by one, dividing it by every smaller number to see if it has any divisors.

This means lots of repeated work and takes a long time.

The Problem

Checking each number manually is slow and tiring.

It's easy to make mistakes by missing divisors or repeating checks.

As numbers get bigger, this method becomes almost impossible to finish quickly.

The Solution

The Sieve of Eratosthenes is like crossing out multiples on a list.

Start with all numbers marked as possible primes.

Then, systematically remove multiples of each prime found, quickly leaving only primes behind.

This saves time and avoids repeated checks.

Before vs After

✗ Before

for (int number = 2; number <= max; number++) {
    bool isPrime = true;
    for (int divisor = 2; divisor < number; divisor++) {
        if (number % divisor == 0) {
            isPrime = false;
            break;
        }
    }
    if (isPrime) Console.WriteLine(number);
}

✓ After

bool[] isPrime = new bool[max + 1];
for (int i = 2; i <= max; i++) isPrime[i] = true;
for (int i = 2; i * i <= max; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= max; j += i) isPrime[j] = false;
    }
}
for (int i = 2; i <= max; i++) {
    if (isPrime[i]) Console.WriteLine(i);
}

What It Enables

This method lets you find all prime numbers up to a large limit quickly and efficiently.

Real Life Example

Finding prime numbers fast is important in cryptography, where secure keys depend on large primes.

Key Takeaways

Manual prime checking is slow and error-prone.

Sieve of Eratosthenes removes multiples to find primes efficiently.

It enables fast prime discovery for large ranges.

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