Sieve of Eratosthenes Find All Primes in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a list of boolean values to mark primes up to n.

DSA Python

n = 20
prime = [[1]] * (n + 1)
prime[0] = prime[1] = False

Drag options to blanks, or click blank then click option'

ATrue

BFalse

CNone

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using False instead of True will mark all numbers as non-prime initially.

Using 0 or None will cause errors in boolean checks.

We initialize a list with True values to mark all numbers as potential primes initially.

2fill in blank

medium

Complete the code to loop through numbers starting from 2 up to the square root of n.

DSA Python

for i in range(2, [1] + 1):
    if prime[i]:
        # Mark multiples of i as not prime

Drag options to blanks, or click blank then click option'

An // 2

Bint(n ** 0.5)

Cn - 1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Looping all the way to n is inefficient.

Using n // 2 is more than needed and slower.

We only need to check numbers up to the square root of n to mark multiples.

3fill in blank

hard

Fix the error in marking multiples of i as not prime starting from i squared.

DSA Python

for j in range(i * i, n + 1, [1]):
    prime[j] = False

Drag options to blanks, or click blank then click option'

Ai

B2

Ci + 1

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using i + 1 or 2 as step size will skip some multiples.

Using j as step size is invalid.

We mark multiples of i by stepping through the list in increments of i.

4fill in blank

hard

Fill both blanks to create a list of all prime numbers up to n.

DSA Python

primes = [[1] for [2] in range(2, n + 1) if prime[[2]]]

Drag options to blanks, or click blank then click option'

Ai

Bj

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variables for loop and collected value causes errors.

Using j instead of i breaks the comprehension.

We collect numbers i where prime[i] is True, iterating i from 2 to n.

5fill in blank

hard

Fill all three blanks to complete the Sieve of Eratosthenes function that returns primes up to n.

DSA Python

def sieve(n):
    prime = [[1]] * (n + 1)
    prime[0] = prime[1] = False
    for i in range(2, [2] + 1):
        if prime[i]:
            for j in range(i * i, n + 1, [3]):
                prime[j] = False
    return [i for i in range(2, n + 1) if prime[i]]

Drag options to blanks, or click blank then click option'

ATrue

Bint(n ** 0.5)

Ci

DFalse

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing with False causes no primes to be found.

Looping beyond square root is inefficient.

Incorrect step size misses multiples.

Initialize prime list with True, loop to square root of n, and mark multiples stepping by i.

Practice

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

easy

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

B. To sort a list of numbers in ascending order

C. To find the greatest common divisor of two numbers

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

   It marks multiples of primes as non-prime, leaving primes unmarked up to the limit.

3. Final Answer:

   To find all prime numbers up to a given limit -> Option A

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 of the following Python code snippets correctly initializes the sieve list for finding primes up to n?

easy

A. sieve = [False] * n

B. sieve = list(range(n))

C. sieve = [True] * (n+1)

D. sieve = [0] * (n-1)

Solution

1. Step 1: Understand sieve initialization

   The sieve list should mark all numbers as potentially prime initially, so all True.

2. Step 2: Check correct length

   It must include index n, so length is n+1.

3. Final Answer:

   sieve = [True] * (n+1) -> Option C

4. Quick Check:

   Initialize all True for 0 to n [OK]

Hint: Use True for all numbers including n [OK]

Common Mistakes:

• Using False instead of True initially
• Not including n in the list length
• Using range instead of boolean list

3. What will be the output of the following code snippet?

n = 10
sieve = [True] * (n+1)
sieve[0], sieve[1] = False, False
for i in range(2, int(n**0.5)+1):
    if sieve[i]:
        for j in range(i*i, n+1, i):
            sieve[j] = False
primes = [i for i in range(n+1) if sieve[i]]
print(primes)

medium

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

B. [2, 3, 5, 7]

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

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

Solution

1. Step 1: Initialize sieve and mark 0,1 as non-prime

   Indices 0 and 1 are set to False, others True initially.

2. Step 2: Mark multiples of primes as False

   For i=2 and i=3 (since sqrt(10) ~3), multiples 4,6,8,9,10 are marked False.

3. Step 3: Collect primes

   Numbers with True are 2,3,5,7.

4. Final Answer:

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

5. Quick Check:

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

Hint: Remember to exclude 0 and 1 as non-prime [OK]

Common Mistakes:

• Including 1 as prime
• Forgetting to start inner loop at i*i
• Marking wrong multiples

4. Identify the error in this Sieve of Eratosthenes code snippet:

n = 15
sieve = [True] * (n+1)
sieve[0], sieve[1] = False, False
for i in range(2, n):
    if sieve[i]:
        for j in range(i*2, n+1, i):
            sieve[j] = False
primes = [i for i in range(n+1) if sieve[i]]
print(primes)

medium

A. Inner loop should start from i*i, not i*2

B. sieve list length should be n, not n+1

C. sieve[0] and sieve[1] should be True

D. Outer loop should run until n+1, not n

Solution

1. Step 1: Check inner loop start index

   Starting from i*2 marks some multiples multiple times, inefficient.

2. Step 2: Correct start is i*i

   Because smaller multiples are already marked by smaller primes.

3. Final Answer:

   Inner loop should start from i*i, not i*2 -> Option A

4. Quick Check:

   Start inner loop at i*i for efficiency [OK]

Hint: Start marking multiples from i squared [OK]

Common Mistakes:

• Starting inner loop at i*2 wastes time
• Incorrect sieve length causes index errors
• Marking 0 or 1 as prime

5. Using the Sieve of Eratosthenes, how many prime numbers are there between 1 and 30 (inclusive)?

hard

A. 8

B. 11

C. 12

D. 10

Solution

1. Step 1: List primes up to 30 using sieve logic

   Primes are 2,3,5,7,11,13,17,19,23,29.

2. Step 2: Count the primes

   Count is 10 primes between 1 and 30 inclusive.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Count primes ≤30 = 10 [OK]

Hint: Count primes carefully, exclude 1 and non-primes [OK]

Common Mistakes:

• Including 1 as prime
• Forgetting to include 29
• Miscounting primes between 20 and 30