Sieve of Eratosthenes Find All Primes in DSA Python - Build from Scratch

Sieve of Eratosthenes Find All Primes

📖 Scenario: You are helping a teacher prepare a list of prime numbers for a math class. The teacher wants to find all prime numbers up to a certain number quickly and easily.

🎯 Goal: Build a program that uses the Sieve of Eratosthenes method to find and print all prime numbers up to a given number.

📋 What You'll Learn

Create a list to represent numbers from 0 to the given limit

Use a variable to store the limit number

Implement the Sieve of Eratosthenes algorithm to mark non-prime numbers

Print the list of prime numbers found

💡 Why This Matters

🌍 Real World

Finding prime numbers is useful in cryptography, computer security, and number theory research.

💼 Career

Understanding prime number algorithms helps in software development roles involving security and optimization.

1

Create the list to represent numbers

Create a list called is_prime with limit + 1 elements, all set to True. This list will help us mark which numbers are prime. Also, set is_prime[0] and is_prime[1] to False because 0 and 1 are not prime.

DSA Python

# Create the is_prime list with True values and set 0 and 1 to False
# Your code here

Hint

Use a list with limit + 1 elements all set to True. Then set the first two elements to False.

2

Set the limit number

Create a variable called limit and set it to 30. This is the number up to which we want to find prime numbers.

DSA Python

limit = 30
is_prime = [True] * (limit + 1)
is_prime[0] = False
is_prime[1] = False
# Your code here

Hint

Just create a variable limit and assign it the value 30.

3

Implement the Sieve of Eratosthenes algorithm

Use a for loop with variable number from 2 to int(limit ** 0.5) + 1. Inside it, use an if statement to check if is_prime[number] is True. If yes, use another for loop with variable multiple starting from number * number to limit + 1 with step number to set is_prime[multiple] to False. This marks multiples of number as not prime.

DSA Python

limit = 30
is_prime = [True] * (limit + 1)
is_prime[0] = False
is_prime[1] = False
# Your code here

Hint

Use nested loops: outer loop from 2 to square root of limit, inner loop marks multiples as False.

4

Print the list of prime numbers

Use a for loop with variable num from 2 to limit + 1. Inside the loop, use an if statement to check if is_prime[num] is True. If yes, print num on the same line separated by spaces.

DSA Python

limit = 30
is_prime = [True] * (limit + 1)
is_prime[0] = False
is_prime[1] = False
for number in range(2, int(limit ** 0.5) + 1):
    if is_prime[number]:
        for multiple in range(number * number, limit + 1, number):
            is_prime[multiple] = False
# Your code here

Hint

Loop through numbers and print those marked True in is_prime on the same line separated by spaces.

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