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.

Practice

1. What is the main purpose of the Sieve of Eratosthenes algorithm?

easy

A. To sort an array of numbers

B. To find all prime numbers up to a given limit

C. To find the greatest common divisor of two numbers

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 B

4. Quick Check:

   Prime finding = B [OK]

Hint: Sieve marks multiples to find primes fast [OK]

Common Mistakes:

• Confusing prime finding with sorting
• Thinking it finds divisors or reverses strings
• Assuming it works for negative numbers

2. Which of the following is the correct way to initialize the sieve array in C for finding primes up to n?

easy

A. int sieve[n+1]; for(int i=0; i<=n; i++) sieve[i] = 1;

B. int sieve[n]; for(int i=1; i

C. int sieve[n+1]; for(int i=0; i<=n; i++) sieve[i] = 0; sieve[0] = sieve[1] = 1;

D. int sieve[n+1]; for(int i=0; i<=n; i++) sieve[i] = i;

Solution

1. Step 1: Understand sieve initialization

   The sieve array uses 1 to mark potential primes initially.

2. Step 2: Check array size and initialization

   Array size should be n+1 to include number n, and all set to 1 (true) initially.

3. Final Answer:

   int sieve[n+1]; for(int i=0; i<=n; i++) sieve[i] = 1; -> Option A

4. Quick Check:

   Initialize all to 1 for primes [OK]

Hint: Initialize all to 1 (true) for prime candidates [OK]

Common Mistakes:

• Using size n instead of n+1
• Initializing with zeros instead of ones
• Marking 0 and 1 as prime initially

3. What will be the output of the following C code snippet using Sieve of Eratosthenes to find primes up to 10?

int n = 10;
int sieve[11];
for(int i=0; i<=n; i++) sieve[i] = 1;
sieve[0] = sieve[1] = 0;
for(int i=2; i*i<=n; i++) {
  if(sieve[i]) {
    for(int j=i*i; j<=n; j+=i) sieve[j] = 0;
  }
}
for(int i=2; i<=n; i++) {
  if(sieve[i]) printf("%d ", i);
}

medium

A. 2 3 4 5 7

B. 1 2 3 5 7

C. 2 3 5 7 9

D. 2 3 5 7

Solution

1. Step 1: Initialize sieve and mark 0,1 as non-prime

   Array sieve marks 0 and 1 as 0 (not prime), others as 1 (prime candidate).

2. Step 2: Mark multiples of primes as non-prime

   For i=2, mark 4,6,8,10 as 0; for i=3, mark 9 as 0.

3. Step 3: Print all indices with sieve[i] = 1

   Primes are 2, 3, 5, 7 only.

4. Final Answer:

   2 3 5 7 -> Option D

5. Quick Check:

   Primes up to 10 = 2 3 5 7 [OK]

Hint: Mark multiples starting from i*i to avoid repeats [OK]

Common Mistakes:

• Printing 1 as prime
• Including non-primes like 4 or 9
• Starting marking multiples from i instead of i*i

4. Identify the error in this Sieve of Eratosthenes code snippet and choose the correct fix:

int n = 20;
int sieve[21];
for(int i=0; i<=n; i++) sieve[i] = 1;
sieve[0] = sieve[1] = 0;
for(int i=2; i<=n; i++) {
  if(sieve[i]) {
    for(int j=2*i; j<=n; j+=i) sieve[j] = 0;
  }
}

medium

A. Remove sieve[0] and sieve[1] assignments

B. Initialize sieve array with zeros instead of ones

C. Change outer loop condition to i*i <= n

D. Start inner loop from j = i instead of 2*i

Solution

1. Step 1: Analyze outer loop condition

   Outer loop runs from 2 to n, but it should run only up to sqrt(n) for efficiency.

2. Step 2: Understand inner loop start

   Inner loop correctly starts from 2*i, but starting from i*i is more optimal.

3. Step 3: Correct the outer loop condition

   Change outer loop to for(i=2; i*i<=n; i++) to avoid unnecessary iterations.

4. Final Answer:

   Change outer loop condition to i*i <= n -> Option C

5. Quick Check:

   Outer loop till sqrt(n) improves sieve [OK]

Hint: Outer loop runs only to sqrt(n) for marking multiples [OK]

Common Mistakes:

• Running outer loop till n wastes time
• Starting inner loop from 2*i instead of i*i (less efficient)
• Not marking 0 and 1 as non-prime

5. You want to find all prime numbers up to 50 using the Sieve of Eratosthenes. After running the sieve, how many numbers will remain marked as prime?

hard

A. 15

B. 16

C. 14

D. 13

Solution

1. Step 1: List primes up to 50

   Primes are: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 (total 15).

2. Step 2: Count primes carefully

   Counting again: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 = 15 primes.

3. Step 3: Check if 1 is counted

   1 is not prime, so total primes = 15.

4. Final Answer:

   15 -> Option A

5. Quick Check:

   Count primes up to 50 = 15 [OK]

Hint: Count known primes or use sieve output count [OK]

Common Mistakes:

• Including 1 as prime
• Miscounting primes between 40 and 50
• Forgetting to exclude non-primes