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

Concept Flow - Sieve of Eratosthenes Find All Primes

Initialize array of size n+1 with True

↓

Set 0 and 1 to False

↓

Start with p = 2 (first prime)

↓

While p * p <= n?

No→End

Yes↓

If array[p

↓

Mark multiples of p as False

↓

Increment p by 1

Back to While check↓

Collect indices with True as primes

↓

Done

↩Back to While check

Start with all numbers marked prime, then repeatedly mark multiples of each prime as not prime, stopping when p squared exceeds n.

Execution Sample

DSA Rust

let n: usize = 10;
let mut sieve: Vec<bool> = vec![true; n + 1];
sieve[0] = false;
sieve[1] = false;
let mut p: usize = 2;
while p * p <= n {
    if sieve[p] {
        let mut multiple = p * p;
        while multiple <= n {
            sieve[multiple] = false;
            multiple += p;
        }
    }
    p += 1;
}
let primes: Vec<usize> = (2..=n).filter(|&i| sieve[i]).collect();

This code initializes a list to mark primes up to 10, then iterates to mark multiples of primes as not prime.

Execution Table

Step	Operation	p	Multiples Marked	Sieve State (index: value)	Notes
1	Initialize sieve	-	-	0:false,1:false,2:true,3:true,4:true,5:true,6:true,7:true,8:true,9:true,10:true	Start with all true except 0 and 1
2	Check p*p <= n	2	-	Same as before	2*2=4 <= 10, continue
3	Mark multiples of 2	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	Multiples of 2 marked false
4	Increment p	3	-	Same as before	p=3
5	Check p*p <= n	3	-	Same as before	3*3=9 <= 10, continue
6	Mark multiples of 3	3	9	0:false,1:false,2:true,3:true,4:false,5:true,6:false,7:true,8:false,9:false,10:false	Multiple 9 marked false
7	Increment p	4	-	Same as before	p=4
8	Check p*p <= n	4	-	Same as before	4*4=16 > 10, stop loop
9	Collect primes	-	-	Primes at indices: 2,3,5,7	Indices with true are primes
10	End	-	-	-	Sieve complete

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

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 8	Final
p	2	3	4	4	4
sieve[4]	true	false	false	false	false
sieve[6]	true	false	false	false	false
sieve[9]	true	true	false	false	false

Key Moments - 3 Insights

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

Because any composite number less than or equal to n must have a factor less than or equal to sqrt(n). Stopping at p * p > n ensures all multiples are marked. See execution_table row 8.

Why do we mark multiples starting from p * p, not from 2 * p?

Multiples less than p * p were already marked by smaller primes. Starting at p * p avoids redundant work. This is implied in the marking steps (rows 3 and 6).

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

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

Visual Quiz - 3 Questions

Look at the execution_table at step 6, which multiples of 3 are marked false?

A 3 and 6

B 6 and 9

C 9 only

D 3, 6, and 9

💡 Hint

Check the 'Multiples Marked' column at step 6 in execution_table.

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

A Step 8

B Step 7

C Step 9

D Step 10

💡 Hint

Look at the 'Check p*p <= n' operation and notes in execution_table rows 7 and 8.

If we increase n to 16, what would be the next value of p after 4?

A 7

B 5

C 6

D 8

💡 Hint

After p=4, p increments by 1 each loop iteration as shown in variable_tracker and execution_table.

Concept Snapshot

Sieve of Eratosthenes:
- Create boolean array up to n, true means prime candidate
- Set 0 and 1 to false (not prime)
- For p from 2 to sqrt(n): if p is prime, mark multiples as false
- Remaining true indices are primes
- Efficiently finds all primes up to n

Full Transcript

The Sieve of Eratosthenes algorithm starts by assuming all numbers from 2 to n are prime. It initializes a list marking all as true except 0 and 1. Then, starting from p=2, it marks all multiples of p as not prime (false). This process repeats while p squared is less than or equal to n. After the loop ends, all indices still marked true are prime numbers. This method efficiently finds all primes up to n by eliminating multiples of each prime.

Practice

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

easy

A. To sort a list of numbers in ascending order

B. To find the greatest common divisor of two numbers

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

D. To calculate the factorial of a number

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 of the algorithm

   It marks multiples of primes as non-prime, leaving primes unmarked 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: Sieve marks multiples to find primes fast [OK]

Common Mistakes:

• Confusing it with sorting algorithms
• Thinking it calculates factorials
• Assuming it finds divisors instead of primes

2. Which Rust code snippet correctly initializes a boolean vector is_prime of size n+1 with all values set to true except for indices 0 and 1?

easy

A. let is_prime = vec![false; n+1]; is_prime[0] = true; is_prime[1] = true;

B. let mut is_prime = vec![true; n+1]; is_prime[0] = false; is_prime[1] = false;

C. let mut is_prime = vec![true; n]; is_prime[0] = false; is_prime[1] = false;

D. let mut is_prime = vec![false; n]; is_prime[0] = true; is_prime[1] = true;

Solution

1. Step 1: Initialize vector with true values

   We want a mutable vector of size n+1 with all true values initially.

2. Step 2: Set indices 0 and 1 to false

   Since 0 and 1 are not prime, we set those positions to false.

3. Final Answer:

   let mut is_prime = vec![true; n+1]; is_prime[0] = false; is_prime[1] = false; -> Option B

4. Quick Check:

   Initialize true vector and mark 0,1 false [OK]

Hint: Use vec![true; n+1] and set 0,1 false [OK]

Common Mistakes:

• Using size n instead of n+1
• Not making vector mutable
• Setting wrong indices to true/false

3. What will be the output of the following Rust code snippet that uses the Sieve of Eratosthenes to find primes up to 10?

let n = 10;
let mut is_prime = vec![true; n+1];
is_prime[0] = false;
is_prime[1] = false;
for i in 2..=((n as f64).sqrt() as usize) {
    if is_prime[i] {
        let mut j = i * i;
        while j <= n {
            is_prime[j] = false;
            j += i;
        }
    }
}
let primes: Vec<usize> = is_prime.iter().enumerate()
    .filter(|&(_, &prime)| prime)
    .map(|(index, _)| index)
    .collect();
println!("{:?}", primes);

medium

A. [2, 3, 5, 7]

B. [1, 2, 3, 5, 7]

C. [2, 3, 4, 5, 7]

D. [0, 2, 3, 5, 7]

Solution

1. Step 1: Initialize and mark non-primes

   Indices 0 and 1 are false. Loop marks multiples of 2 and 3 as false.

2. Step 2: Collect indices marked true

   Only 2, 3, 5, and 7 remain true and are collected as primes.

3. Final Answer:

   [2, 3, 5, 7] -> Option A

4. Quick Check:

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

Hint: Primes under 10 are 2,3,5,7 only [OK]

Common Mistakes:

• Including 1 or 0 as prime
• Including 4 which is not prime
• Not starting j from i*i

4. Identify the bug in this Rust code snippet implementing the Sieve of Eratosthenes for n = 15:

let n = 15;
let mut is_prime = vec![true; n+1];
is_prime[0] = false;
is_prime[1] = false;
for i in 2..n {
    if is_prime[i] {
        let mut j = i * 2;
        while j <= n {
            is_prime[j] = false;
            j += i;
        }
    }
}

medium

A. Indices 0 and 1 should be set to true

B. The vector size should be n, not n+1

C. The outer loop should run from 2 to sqrt(n), not 2 to n

D. The inner loop should start from i * i, not i * 2

Solution

1. Step 1: Check inner loop start index

   Starting from i*2 marks some numbers multiple times, less efficient.

2. Step 2: Correct start is i*i for marking multiples

   Because smaller multiples are already marked by smaller primes.

3. Final Answer:

   The inner loop should start from i * i, not i * 2 -> Option D

4. Quick Check:

   Start marking multiples from i*i for efficiency [OK]

Hint: Start marking multiples from i squared [OK]

Common Mistakes:

• Starting inner loop from i*2 wastes time
• Looping outer from 2 to n instead of sqrt(n)
• Wrong vector size causing index errors

5. You want to find all prime numbers up to 50 using the Sieve of Eratosthenes in Rust. After running the sieve, you want to return a vector of primes but exclude the prime number 2 from the result. Which modification to the code below achieves this?

let n = 50;
let mut is_prime = vec![true; n+1];
is_prime[0] = false;
is_prime[1] = false;
for i in 2..=((n as f64).sqrt() as usize) {
    if is_prime[i] {
        let mut j = i * i;
        while j <= n {
            is_prime[j] = false;
            j += i;
        }
    }
}
let primes: Vec<usize> = is_prime.iter().enumerate()
    .filter(|&(_, &prime)| prime)
    .map(|(index, _)| index)
    .collect();

hard

A. Add a filter after collecting primes: primes.into_iter().filter(|&x| x != 2).collect()

B. Set is_prime[2] = false before the outer loop

C. Start outer loop from 3 instead of 2

D. Remove is_prime[0] = false line

Solution

1. Step 1: Understand the sieve marks primes correctly

   All primes including 2 are marked true in is_prime.

2. Step 2: Exclude 2 after collecting primes

   Filtering out 2 after collecting primes avoids affecting sieve logic.

3. Final Answer:

   Add a filter after collecting primes: primes.into_iter().filter(|&x| x != 2).collect() -> Option A

4. Quick Check:

   Filter out 2 after sieve to exclude it [OK]

Hint: Filter out 2 after collecting primes [OK]

Common Mistakes:

• Setting is_prime[2] = false breaks sieve correctness
• Starting loop from 3 misses marking multiples of 2
• Removing is_prime[0] = false causes wrong prime marking