Sieve of Eratosthenes Find All Primes in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sieve for n=10

What is the output list of primes generated by the Sieve of Eratosthenes for n=10?

DSA Python

def sieve(n):
    primes = [True] * (n+1)
    primes[0] = primes[1] = False
    p = 2
    while p * p <= n:
        if primes[p]:
            for i in range(p * p, n+1, p):
                primes[i] = False
        p += 1
    return [x for x in range(n+1) if primes[x]]

print(sieve(10))

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

B [2, 3, 4, 5, 7]

C [2, 3, 5, 7]

D [2, 3, 5, 7, 9]

💡 Hint

Remember primes are numbers greater than 1 with no divisors other than 1 and themselves.

The sieve marks multiples of primes as not prime. For n=10, primes are 2, 3, 5, and 7 only.

❓ Predict Output

intermediate

Number of primes up to 20

How many prime numbers are there up to 20 using the Sieve of Eratosthenes?

DSA Python

def sieve_count(n):
    primes = [True] * (n+1)
    primes[0] = primes[1] = False
    p = 2
    while p * p <= n:
        if primes[p]:
            for i in range(p * p, n+1, p):
                primes[i] = False
        p += 1
    return sum(primes)

print(sieve_count(20))

A 7

B 8

C 9

D 6

💡 Hint

Count primes: 2,3,5,7,11,13,17,19

There are 8 primes up to 20: 2,3,5,7,11,13,17,19.

🔧 Debug

advanced

Identify the error in this sieve implementation

What error will this code produce when run with n=10?

DSA Python

def sieve_bug(n):
    primes = [True] * n
    primes[0] = primes[1] = False
    p = 2
    while p * p <= n:
        if primes[p]:
            for i in range(p * p, n+1, p):
                primes[i] = False
        p += 1
    return [x for x in range(n) if primes[x]]

print(sieve_bug(10))

A IndexError

B [2, 3, 5, 7]

C TypeError

D [2, 3, 5, 7, 9]

💡 Hint

Check the list size and the indices accessed in the loop.

The list primes has length n=10, but the loop tries to access primes[10], causing IndexError.

❓ Predict Output

advanced

Output of primes for n=1

What is the output of the sieve function when n=1?

DSA Python

def sieve(n):
    primes = [True] * (n+1)
    primes[0] = primes[1] = False
    p = 2
    while p * p <= n:
        if primes[p]:
            for i in range(p * p, n+1, p):
                primes[i] = False
        p += 1
    return [x for x in range(n+1) if primes[x]]

print(sieve(1))

A [1]

B [2]

C [0, 1]

D []

💡 Hint

Primes start from 2, so no primes exist for n=1.

Since 0 and 1 are not prime, and n=1, the output list is empty.

🧠 Conceptual

expert

Why does the sieve start marking multiples from p*p?

In the Sieve of Eratosthenes, why do we start marking multiples of a prime p from p*p instead of 2*p?

A Because all smaller multiples of p were already marked by smaller primes

B Because p*p is the smallest prime number

C Because 2*p is not a multiple of p

D Because starting from 2*p would miss some prime numbers

💡 Hint

Think about when smaller multiples get marked.

Multiples less than p*p are already marked by smaller primes, so starting at p*p avoids redundant work.