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.