Sieve of Eratosthenes Find All Primes in DSA Python - 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 certain 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 current 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 list or array of boolean values where each index represents a number and the value indicates if it is prime (True) or not (False).

intermediate

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

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

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 by smaller numbers.

What number do you start with when using the Sieve of Eratosthenes to find primes?

A 3

B 1

C 0

D 2

The sieve starts from 2, the smallest prime number.

When marking multiples of a prime p, from which number should you start marking?

A p * p

B p + 1

C p * 2

D 1

Start marking from p squared to avoid marking multiples already handled by smaller primes.

What does a True value in the sieve's boolean list represent?

A The number is prime

B The number is composite

C The number is even

D The number is odd

True means the number is still considered prime.

Which of these is NOT a step in the Sieve of Eratosthenes?

A Mark multiples of primes as not prime

B Check divisibility of each number by all smaller numbers

C Start from 2 and go up to the square root of the limit

D Return all numbers still marked as prime

The sieve does not check divisibility individually; it marks multiples instead.

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

A It uses less memory

B It does not require any loops

C It finds all primes up to a limit efficiently

D It works only for small numbers

The sieve efficiently finds all primes up to a limit by marking multiples.

Explain how the Sieve of Eratosthenes algorithm 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 dividing by smaller numbers.

Focus on how the sieve reduces repeated work.