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

↓

Is p * p <= n?

No→End

|Yes↓

If array[p

↓

Mark multiples of p as False

↓

Increment p by 1

↩Back to check p * p <= n

Start with all numbers marked prime, then repeatedly mark multiples of each prime as not prime until reaching sqrt(n).

Execution Sample

DSA C++

int n = 10;
vector<bool> prime(n+1, 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;
  }
}

Marks non-prime numbers up to 10 using the sieve method.

Execution Table

Step	Operation	Current p	Multiples Marked False	Array State (index:prime)
1	Initialize array with True, set 0 and 1 as False	-	-	0:false,1:false,2:true,3:true,4:true,5:true,6:true,7:true,8:true,9:true,10:true
2	Check p=2, p*p=4 <= 10	2	-	Same as previous
3	Mark multiples of 2 false	2	4,6,8,10	0:false,1:false,2:true,3:true,4:false,5:true,6:false,7:true,8:false,9:true,10:false
4	Increment p to 3, check p*p=9 <= 10	3	-	Same as previous
5	Mark multiples of 3 false	3	9	0:false,1:false,2:true,3:true,4:false,5:true,6:false,7:true,8:false,9:false,10:false
6	Increment p to 4, check p*p=16 > 10	4	-	Same as previous
7	End loop as p*p > n	-	-	Final array state as above

💡 Loop ends when p*p > n (4*4=16 > 10)

Variable Tracker

Variable	Start	After Step 3	After Step 5	Final
p	-	2	3	4 (loop ends)
prime array	all true except 0,1 false	multiples of 2 false	multiples of 3 false	final sieve array

Key Moments - 3 Insights

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

Because smaller multiples of p were already marked by smaller primes. For example, 2*3=6 was marked when p=2. This is shown in execution_table row 3 where marking starts 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). So checking beyond sqrt(n) is unnecessary. This is shown in execution_table row 6 and exit_note.

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

Because 0 and 1 are not prime numbers by definition. This is initialized in execution_table row 1.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, which multiples of 2 are marked false?

A 2, 4, 6, 8

B 3, 6, 9

C 4, 6, 8, 10

D 5, 7, 9

💡 Hint

Check the 'Multiples Marked False' column in Step 3 of execution_table.

At which step does the loop end because p*p > n?

A Step 6

B Step 7

C Step 5

D Step 4

💡 Hint

Look at the 'Operation' and 'Current p' columns in execution_table rows 6 and 7.

If we change n to 25, how would the condition p*p <= n affect the number of iterations?

A Fewer iterations because 25 is larger

B More iterations because sqrt(25)=5, so p goes up to 5

C Same number of iterations as n=10

D No iterations because p*p > n immediately

💡 Hint

Refer to the concept_flow where loop continues while p*p <= n.

Concept Snapshot

Sieve of Eratosthenes finds primes up to n.
Initialize array with True except 0 and 1.
For p from 2 to sqrt(n), mark multiples of p as False starting at p*p.
Remaining True indices are primes.
Stops when p*p > n.

Full Transcript

The Sieve of Eratosthenes algorithm starts by creating an array of booleans representing numbers from 0 to n, initially marking all as true except 0 and 1 which are not prime. Then, starting from p=2, it checks if p squared is less than or equal to n. If yes and if p is still marked true, it marks all multiples of p starting from p squared as false because they are not prime. This process repeats by incrementing p until p squared exceeds n. The final array shows which numbers are prime (true) and which are not (false).

Practice

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

easy

A. To calculate the factorial of a number

B. To sort an array of numbers

C. To find the greatest common divisor of two numbers

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

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, leaving primes unmarked up to the limit.

3. Final Answer:

   To find all prime numbers up to a given limit -> Option D

4. Quick Check:

   Sieve finds primes = D [OK]

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

Common Mistakes:

• Confusing sieve with sorting algorithms
• Thinking it calculates factorial or gcd
• Assuming it finds primes beyond the limit

2. Which of the following C++ code snippets correctly initializes the sieve array for numbers up to n?

easy

A. std::vector<bool> sieve(n+1, true); sieve[0] = sieve[1] = false;

B. std::vector<int> sieve(n, 0); sieve[0] = sieve[1] = 1;

C. bool sieve[n]; for(int i=0; i

D. std::vector<bool> sieve(n+1, false); sieve[0] = sieve[1] = true;

Solution

1. Step 1: Check initialization for prime marking

   The sieve should start with all true except 0 and 1, which are not prime.

2. Step 2: Validate code correctness

   std::vector<bool> sieve(n+1, true); sieve[0] = sieve[1] = false; uses a vector<bool> with size n+1, sets all true, then marks 0 and 1 false correctly.

3. Final Answer:

   std::vector<bool> sieve(n+1, true); sieve[0] = sieve[1] = false; -> Option A

4. Quick Check:

   Initialize sieve true except 0,1 false = A [OK]

Hint: Start sieve with true, mark 0 and 1 false [OK]

Common Mistakes:

• Using wrong data type for sieve array
• Not marking 0 and 1 as non-prime
• Initializing all false instead of true

3. What will be the output primes printed by the following C++ code snippet using Sieve of Eratosthenes for n = 10?

int n = 10;
std::vector<bool> sieve(n+1, true);
sieve[0] = sieve[1] = false;
for (int i = 2; i * i <= n; i++) {
  if (sieve[i]) {
    for (int j = i * i; j <= n; j += i) {
      sieve[j] = false;
    }
  }
}
for (int i = 2; i <= n; i++) {
  if (sieve[i]) std::cout << i << " ";
}

medium

A. 2 3 4 5 7

B. 2 3 5 7

C. 1 2 3 5 7

D. 2 3 5 7 9

Solution

1. Step 1: Run sieve marking multiples

   Multiples of 2 (4,6,8,10) and 3 (9) are marked false.

2. Step 2: Identify primes left true

   Numbers 2, 3, 5, 7 remain true and are printed.

3. Final Answer:

   2 3 5 7 -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Including non-primes like 4 or 9
• Printing 1 as prime
• Not starting inner loop from i*i

4. Identify the error in the following Sieve of Eratosthenes code snippet and select the fix:

int n = 20;
std::vector<bool> sieve(n+1, true);
sieve[0] = sieve[1] = false;
for (int i = 2; i <= n; i++) {
  if (sieve[i]) {
    for (int j = i * 2; j <= n; j += i) {
      sieve[j] = false;
    }
  }
}

medium

A. Start inner loop from j = i + 1

B. Initialize sieve with false instead of true

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

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

Solution

1. Step 1: Analyze loop conditions

   The outer loop runs up to n, which is inefficient and unnecessary.

2. Step 2: Correct loop to optimize marking

   Changing outer loop to run while i * i <= n avoids redundant checks and improves performance.

3. Final Answer:

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

4. Quick Check:

   Outer loop limit = i*i <= n [OK]

Hint: Outer loop runs till i*i <= n for efficiency [OK]

Common Mistakes:

• Running outer loop till n wastes time
• Starting inner loop incorrectly
• Not marking 0 and 1 false

5. You want to find all prime numbers up to n = 50 using the Sieve of Eratosthenes. After running the sieve, how many primes will be found?

hard

A. 15

B. 16

C. 14

D. 17

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 correctly

   Counting carefully confirms total primes up to 50 is 15.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Count primes ≤ 50 = 15 [OK]

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

Common Mistakes:

• Counting non-primes like 1 or 9
• Including primes beyond 50
• Miscounting total primes