Sieve of Eratosthenes Find All Primes in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Sieve of Eratosthenes?

It is a method to find all prime numbers up to a given limit by repeatedly marking the multiples of each prime number starting from 2.

intermediate

Why do we start marking multiples from the square of the prime in the Sieve of Eratosthenes?

Because all smaller multiples of the prime have already been marked by smaller primes, so starting from the square avoids redundant work.

beginner

In the Sieve of Eratosthenes, what data structure is commonly used to keep track of prime candidates?

A boolean array where each index represents a number, and the value indicates whether it is still considered prime (true) or marked as not prime (false).

intermediate

What is the time complexity of the Sieve of Eratosthenes algorithm?

The time complexity is O(n log log n), which is efficient for finding all primes up to n.

beginner

How does the Sieve of Eratosthenes differ from checking primality by trial division?

The sieve finds all primes up to a limit at once by marking multiples, while trial division checks each number individually by dividing it by smaller numbers.

What number do we start marking multiples from for each prime in the Sieve of Eratosthenes?

A The square of the prime

B The prime itself

C One

D Two times the prime

We start marking multiples from the square of the prime because smaller multiples have already been marked by smaller primes.

What does a 'false' value in the boolean array represent in the sieve?

A The number is unknown

B The number is prime

C The number is not prime

D The number is zero

False means the number has been marked as not prime (a multiple of some prime).

What is the first prime number used in the Sieve of Eratosthenes?

A 2

B 3

C 1

D 0

2 is the smallest prime number and the first used in the sieve.

Which of these best describes the Sieve of Eratosthenes?

A A sorting algorithm

B A graph traversal algorithm

C A searching algorithm

D A prime number generation algorithm

The sieve is used to generate all prime numbers up to a limit.

What is the main benefit of using the Sieve of Eratosthenes over checking each number individually?

A It uses less memory

B It is faster for large ranges

C It works only for small numbers

D It finds composite numbers only

The sieve is faster for finding all primes up to a large number compared to checking each number individually.

Explain how the Sieve of Eratosthenes finds all prime numbers up to a given number.

Think about crossing out multiples step by step.

Describe why the Sieve of Eratosthenes is more efficient than checking each number's primality by division.

Consider how many times each number is processed.

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