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 certain limit by repeatedly marking the multiples of each prime number starting from 2.
Click to reveal answer
intermediate
Why do we start marking multiples from the square of the prime number in the Sieve of Eratosthenes?
Because all smaller multiples of that prime have already been marked by smaller primes, so starting from the square avoids redundant work.
Click to reveal answer
beginner
In the Sieve of Eratosthenes, what does a 'true' value in the boolean array represent?
It means the number at that index is currently considered prime (not marked as a multiple of any smaller prime).
Click to reveal answer
intermediate
What is the time complexity of the Sieve of Eratosthenes algorithm?
The time complexity is O(n log log n), which is very efficient for finding primes up to n.
Click to reveal answer
beginner
How does the Sieve of Eratosthenes help in real-life situations?
It helps quickly find prime numbers which are useful in cryptography, hashing, and random number generation.
Click to reveal answer
What is the first prime number used to start the sieve?
✗ Incorrect
The sieve starts with 2, the smallest prime number.
When marking multiples of a prime p, from which number do we start?
✗ Incorrect
We start marking from p squared to avoid marking multiples already handled.
What does a false value in the sieve array mean after processing?
✗ Incorrect
False means the number was marked as a multiple of a prime, so it is composite.
Which data structure is commonly used to implement the sieve?
✗ Incorrect
A boolean array tracks whether each number is prime (true) or not (false).
What is the main benefit of the Sieve of Eratosthenes compared to checking each number individually?
✗ Incorrect
The sieve is much faster than checking primality one by one for large ranges.
Explain how the Sieve of Eratosthenes finds all prime numbers up to a given number n.
Think about crossing out multiples step by step.
You got /4 concepts.
Describe why starting to mark multiples from p squared is an optimization in the sieve.
Consider what happens to multiples less than p squared.
You got /3 concepts.