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

Concept Flow - Sieve of Eratosthenes Find All Primes

Create array of size n+1, all True

↓

Set 0 and 1 as False

↓

Start with p=2

↓

Is p*p <= n?

No→Stop

Yes↓

Mark multiples of p as False

↓

Increment p to next True

↓

Repeat loop

↓

Collect indices with True as primes

Start with an array marking all numbers as prime candidates. Repeatedly mark multiples of each prime as not prime, then collect remaining primes.

Execution Sample

DSA C

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

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

Execution Table

Step	Operation	Current p	Mark Multiples	Array State (index:prime)
1	Initialize array	-	None	0:F 1:F 2:T 3:T 4:T 5:T 6:T 7:T 8:T 9:T 10:T
2	Start p=2	2	Mark multiples of 2	0:F 1:F 2:T 3:T 4:F 5:T 6:F 7:T 8:F 9:T 10:F
3	Increment p=3	3	Mark multiples of 3	0:F 1:F 2:T 3:T 4:F 5:T 6:F 7:T 8:F 9:F 10:F
4	Increment p=4	4	Skip (4 is False)	0:F 1:F 2:T 3:T 4:F 5:T 6:F 7:T 8:F 9:F 10:F
5	Increment p=5	5	p*p=25 > 10 stop	0:F 1:F 2:T 3:T 4:F 5:T 6:F 7:T 8:F 9:F 10:F
6	Collect primes	-	Indices with True	Primes: 2, 3, 5, 7

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
p	-	2	3	4	5	-
prime array	all True except 0 and 1 False	multiples of 2 False	multiples of 3 False	unchanged (4 False)	unchanged (stop)	final sieve
marked multiples	none	4,6,8,10	9	none	none	none

Key Moments - 3 Insights

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

Because smaller multiples like 2*p, 3*p were already marked by smaller primes. Starting at p*p avoids redundant work, as shown in step 2 where multiples start at 4 (2*2).

Why does the loop stop 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). Once p*p > n, all composites are marked, so no need to continue (see step 5).

Why are 0 and 1 set to False at the start?

0 and 1 are not prime numbers by definition, so they are marked False before starting the sieve (step 1).

Visual Quiz - 3 Questions

Look at the execution table at Step 3. Which multiples of 3 are marked False?

A 6 and 9

B 3 and 6

C 9 and 12

D 3 and 9

💡 Hint

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

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

A Step 2

B Step 3

C Step 5

D Step 6

💡 Hint

Look at the 'Operation' and 'Current p' columns where p*p > n is mentioned.

If we did not set prime[0] and prime[1] to False at the start, what would happen?

A The algorithm would run infinitely

B 0 and 1 would be incorrectly included as primes

C The algorithm would mark all numbers False

D No change in output

💡 Hint

Refer to the initial array state in Step 1 and the definition of primes.

Concept Snapshot

Sieve of Eratosthenes:
- Create boolean array up to n, True means prime candidate
- Set 0 and 1 to False
- For p from 2 to sqrt(n):
  - If prime[p] is True, mark multiples p*p, p*p+p, ... False
- Remaining True indices are primes
- Stops when p*p > n
- Efficiently finds all primes up to n

Full Transcript

The Sieve of Eratosthenes finds all prime numbers up to a number n by creating an array marking all numbers as prime candidates. It sets 0 and 1 as not prime. Starting from p=2, it marks all multiples of p as not prime, beginning at p squared to avoid redundant marking. This repeats for each p until p squared exceeds n. The remaining numbers marked True are primes. This method efficiently eliminates non-primes and collects primes up to n.