Sieve of Eratosthenes Find All Primes in DSA Rust

Mental Model

We mark multiples of each prime number as not prime, so only primes remain unmarked.

Analogy: Imagine a list of numbers like a row of boxes. You paint over every multiple of 2, then every multiple of 3, and so on, leaving only boxes with prime numbers unpainted.

Numbers: 2 3 4 5 6 7 8 9 10
Marks:  _ _ X _ X _ X X  X
(Here X means crossed out as not prime)

Dry Run Walkthrough

Input: Find all primes up to 10

Goal: Identify all prime numbers from 2 to 10 using the sieve method

Step 1: Start with list 2 to 10, all marked as prime (true)

2:true 3:true 4:true 5:true 6:true 7:true 8:true 9:true 10:true

Why: We assume all numbers are prime initially

Step 2: Mark multiples of 2 (except 2) as not prime

2:true 3:true 4:false 5:true 6:false 7:true 8:false 9:true 10:false

Why: Multiples of 2 cannot be prime

Step 3: Move to next prime 3, mark multiples of 3 (except 3) as not prime

2:true 3:true 4:false 5:true 6:false 7:true 8:false 9:false 10:false

Why: Multiples of 3 cannot be prime

Step 4: Next prime is 5, mark multiples of 5 (except 5) as not prime

2:true 3:true 4:false 5:true 6:false 7:true 8:false 9:false 10:false

Why: No multiples of 5 less than or equal to 10 except 10 which is already marked

Step 5: Next prime is 7, mark multiples of 7 (except 7) as not prime

2:true 3:true 4:false 5:true 6:false 7:true 8:false 9:false 10:false

Why: No multiples of 7 less than or equal to 10 except 7 itself

Result:

Primes are numbers marked true: 2 -> 3 -> 5 -> 7 -> null

Annotated Code

DSA Rust

fn sieve_of_eratosthenes(n: usize) -> Vec<usize> {
    let mut is_prime = vec![true; n + 1];
    if n >= 0 { is_prime[0] = false; } // 0 is not prime
    if n >= 1 { is_prime[1] = false; } // 1 is not prime

    let limit = (n as f64).sqrt() as usize;
    for i in 2..=limit {
        if is_prime[i] {
            // Mark multiples of i as not prime
            let mut multiple = i * i;
            while multiple <= n {
                is_prime[multiple] = false; // mark multiple as not prime
                multiple += i; // move to next multiple
            }
        }
    }

    // Collect all primes
    is_prime.iter().enumerate()
        .filter_map(|(num, &prime)| if prime { Some(num) } else { None })
        .collect()
}

fn main() {
    let n = 10;
    let primes = sieve_of_eratosthenes(n);
    for p in primes {
        print!("{} -> ", p);
    }
    println!("null");
}

let mut is_prime = vec![true; n + 1];

Initialize all numbers as prime candidates

is_prime[0] = false; // 0 is not prime is_prime[1] = false; // 1 is not prime

Mark 0 and 1 as not prime explicitly

let limit = (n as f64).sqrt() as usize;

Only need to check up to square root of n

for i in 2..=limit {

Iterate through possible prime candidates

if is_prime[i] {

If i is still marked prime, mark its multiples

let mut multiple = i * i;

Start marking multiples from i squared

while multiple <= n {

Mark all multiples of i as not prime

is_prime[multiple] = false;

Mark current multiple as not prime

multiple += i;

Move to next multiple of i

is_prime.iter().enumerate().filter_map(|(num, &prime)| if prime { Some(num) } else { None }).collect()

Collect all numbers still marked prime

Output

2 -> 3 -> 5 -> 7 -> null

Complexity Analysis

Time: O(n log log n) because we mark multiples of primes efficiently up to n

Space: O(n) because we store a boolean array for all numbers up to n

vs Alternative: Compared to checking each number's primality individually (O(n√n)), sieve is much faster for large n

Edge Cases

n = 0 or n = 1

No primes found, returns empty list

DSA Rust

if n >= 0 { is_prime[0] = false; } // 0 is not prime
if n >= 1 { is_prime[1] = false; } // 1 is not prime

n = 2

Returns [2] as the only prime

DSA Rust

for i in 2..=limit { if is_prime[i] { ... } }

n is a prime number

Includes n in the output primes

DSA Rust

is_prime.iter().enumerate().filter_map(|(num, &prime)| if prime { Some(num) } else { None }).collect()

When to Use This Pattern

When asked to find all primes up to a number efficiently, reach for the Sieve of Eratosthenes because it marks multiples to eliminate non-primes quickly.

Common Mistakes

Mistake: Starting to mark multiples from 2*i instead of i*i
Fix: Start marking from i*i because smaller multiples were already marked by smaller primes

Mistake: Not limiting the outer loop to sqrt(n)
Fix: Limit outer loop to sqrt(n) to avoid unnecessary checks

Summary

It finds all prime numbers up to a given limit by marking multiples of primes as not prime.

Use it when you need a fast way to list all primes up to a number.

The key insight is that multiples of a prime smaller than its square are already marked by smaller primes.

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