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.

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