ECX 30 Days of Code and Design
Day 23
Sieve of Eratosthenes
Task
The sieve of Eratosthenes is an ancient algorithm for finding all primes less than a given value N. It operates as follows:
Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n)
Initially, let p equal 2, the smallest prime number
Enumerate the multiples of p by counting in increments of p from 2p to n, and mark them in the list (these will be 2p, 3p, 4p, …; the p itself should not be marked)
Find the smallest number in the list greater than p that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3
When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n See more: Sieve of Eratosthenes.
Using the Sieve of Eratosthenes (as described above), Write a function that takes in an integer as input, and returns a list containing all primes less than that input number.
My Approach
Below is the full code. It would be explained in bits throughout this article.
def sieve_of_eratosthenes(user_input):
"""Prints out prime numbers below the argument inputted"""
list_of_composite = [] # To store composite numbers
list_of_prime = [] # To store prime numbers
prime_num = 2 # Starting from the first prime number
multiplier = 2 # To get the multiples of the prime number
multiples = 0 # Store the values of multiples of prime numbers
while prime_num < user_input:
if prime_num in list_of_composite:
prime_num += 1
continue
else:
list_of_prime.append(prime_num)
# Finding multiples of prime numbers and storing them in composite list
while multiples < user_input:
multiples = prime_num * multiplier
# Prevent inputting the same number in composite list
if multiples in list_of_composite:
multiplier += 1
continue
# Input multiples of prime not yet in the composite list
else:
list_of_composite.append(multiples)
multiplier += 1
# Reverts the multiplier and multiples variable to zero to prime number to a new number
multiples = 0
multiplier = 2
prime_num += 1
print(list_of_prime)
print(' Find Prime Numbers Using Sieve of Eratosthenes '.center(50, '*'))
print('Find the prime numbers below a certain number.')
try:
user_inputs = int(input('Enter number: '))
# Function Call
sieve_of_eratosthenes(user_inputs)
except ValueError:
print('Invalid input! Enter only integers.')
First, we define the function, sieve_of_erastosthenes(), which would print out the prime numbers below the number inputted by the user. Next, we create a list which would contain the composite (non-prime) numbers, and another list which would contain the prime numbers. We then create variables; prime_num would have values 2 to (user input – 1). If it is found to be a prime number, it is added to list_of_prime, else it is added to list_of_composite; multiplier would be used to get the multiples of every prime number below the user input, while multiples stores the values, and is added to list_of_composite if it is not already in there.
def sieve_of_eratosthenes(user_input):
list_of_composite = []
list_of_prime = []
prime_num = 2
multiplier = 2
multiples = 0
Next, using a while loop, we increase the variable, prime_num, from 2 to the (user’s input - 1). We check if the user input is already in list_of_composite; if yes, we increase its value and go to the start of the loop, else, we add the value to list_of_prime, after which we get it multiples below the user’s input and add them to list_of_composite. When we get all its multiples, we increase the value of prime_num. When the prime numbers below the user’s input have been gotten, the function prints out the list items of list_of_prime.
while prime_num < user_input:
if prime_num in list_of_composite:
prime_num += 1
continue
else:
list_of_prime.append(prime_num)
while multiples < user_input:
multiples = prime_num * multiplier
if multiples in list_of_composite:
multiplier += 1
continue
else:
list_of_composite.append(multiples)
multiplier += 1
multiples = 0
multiplier = 2
prime_num += 1
print(list_of_prime)
Finally, we ask the user to input an integer and pass the input to the function, which prints out a list of prime numbers below the user’s input.
print(' Find Prime Numbers Using Sieve of Eratosthenes '.center(50, '*'))
print('Find the prime numbers below a certain number.')
try:
user_inputs = int(input('Enter number: '))
sieve_of_eratosthenes(user_inputs)
except ValueError:
print('Invalid input! Enter only integers.')
Output
If a user inputs 100, s/he gets;
* Find Prime Numbers Using Sieve of Eratosthenes *
Find the prime numbers below a certain number.
Enter number: 100
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Run the code on Replit.