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.