Sieve of Eratosthenes Find All Primes in DSA C# - Execution Trace

Concept Flow - Sieve of Eratosthenes Find All Primes

Initialize array of size n+1 with True

↓

Set 0 and 1 as False

↓

Start with p=2 (first prime)

↓

Is p*p <= n?

No→Collect all indices with True as primes

Yes↓

Mark multiples of p as False

↓

Increment p to next True

↩Back to check p*p <= n

The sieve marks multiples of each prime starting from 2 as not prime, repeating until p squared exceeds n, then collects all primes.

Execution Sample

DSA C#

int n = 10;
bool[] isPrime = new bool[n + 1];
for (int i = 2; i <= n; i++) isPrime[i] = true;
for (int p = 2; p * p <= n; p++) {
  if (isPrime[p]) {
    for (int i = p * p; i <= n; i += p) isPrime[i] = false;
  }
}

This code finds all prime numbers up to 10 using the sieve method.

Execution Table

Step	Operation	Current p	Marking Multiples	Array State (index:prime?)	Notes
1	Initialize array	-	-	0:F,1:F,2:T,3:T,4:T,5:T,6:T,7:T,8:T,9:T,10:T	Set 0 and 1 as not prime, others true
2	Check p=2, p*p=4 <= 10	2	Mark multiples 4,6,8,10 as False	0:F,1:F,2:T,3:T,4:F,5:T,6:F,7:T,8:F,9:T,10:F	Multiples of 2 marked not prime
3	Increment p to 3 (next True)	3	Mark multiples 9 as False	0:F,1:F,2:T,3:T,4:F,5:T,6:F,7:T,8:F,9:F,10:F	Multiple 9 marked not prime
4	Increment p to 4 (False), skip	4	-	Same as previous	4 is not prime, skip
5	p=5, p*p=25 > 10 stop	5	-	Same as previous	Stop as p*p > n
6	Collect primes	-	-	Primes at indices: 2,3,5,7	Final primes collected

💡 Stop when p*p > n (5*5=25 > 10), sieve complete

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
p	-	2	3	4	5	5	5
isPrime[2]	False	True	True	True	True	True	True
isPrime[4]	False	True	False	False	False	False	False
isPrime[9]	False	True	True	False	False	False	False

Key Moments - 3 Insights

Why do we start marking multiples from p*p and not from 2*p?

Because all smaller multiples of p (like 2*p, 3*p, ...) were already marked by smaller primes. See Step 2 where marking starts at 4 (2*2).

Why do we stop the outer loop when p*p > n?

Because any composite number less than or equal to n must have a factor less than or equal to sqrt(n). See Step 5 where p=5 and 5*5=25 > 10, so we stop.

Why do we skip p when isPrime[p] is False?

Because p is already marked as not prime, so no need to mark its multiples. See Step 4 where p=4 is False and skipped.

Visual Quiz - 3 Questions

Look at the execution table at Step 3, which multiples of 3 are marked as not prime?

A 6 and 9

B 9 only

C 3 and 6

D 3 only

💡 Hint

Check the 'Marking Multiples' and 'Array State' columns at Step 3.

At which step does the algorithm stop marking multiples because p*p > n?

A Step 5

B Step 6

C Step 4

D Step 3

💡 Hint

Look at the 'Notes' column for when p*p > n condition is met.

If we started marking multiples from 2*p instead of p*p, what would happen?

A The algorithm would run faster

B The algorithm would miss some non-primes

C Some multiples would be marked twice

D No change in marking

💡 Hint

Refer to the key moment about why marking starts at p*p.

Concept Snapshot

Sieve of Eratosthenes:
- Create boolean array up to n, true means prime candidate
- Set 0 and 1 as false
- For p from 2 to sqrt(n):
  - If isPrime[p] true, mark multiples from p*p false
- Collect indices still true as primes
- Stops when p*p > n

Full Transcript

The Sieve of Eratosthenes finds all prime numbers up to a number n by marking multiples of each prime as not prime. We start with an array where all numbers from 2 to n are true (possible primes). We then start with p=2, the first prime, and mark all multiples of p starting from p squared as false because they cannot be prime. We repeat this for the next number still marked true. We stop when p squared is greater than n because all composites have been marked by then. Finally, all indices still true are primes. This method efficiently finds primes by eliminating multiples step-by-step.

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