Python Sieve of Eratosthenes

In this article, we will learn how to implement Python Sieve of Eratosthenes to find Prime Numbers. Sieve of Eratosthenes is an ancient algorithm used to find the prime numbers up to any given limit and it is one of the efficient ways to find prime numbers.

How Sieve of Eratosthenes works?

Sieve of Eratosthenes works on the principle of identifying the smallest prime number and eliminating all the multiples of that prime number within the range and so on.

To start simple, let’s find out the prime numbers between 1 to 20

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

We will get rid of 1 because the definition of ‘prime’ excludes 1

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Now the smallest prime is 2, and any number which is divisible by 2 is not a prime number right? so, let keep 2 and strikeout all the numbers which are divisible by 2

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

We will have the below number only, this has wiped out almost half of the list which we started with

2 3 5 7 9 11 13 15 17 19

The next prime is 3, repeat the same process and strike out all the multiples of 3

2 3 5 7 9 11 13 15 17 19 –> 2 3 5 7 11 13 17 19

Likewise, this process repeats until we get all the leftover numbers are prime numbers. In our case, we just need two iterations to get all the prime numbers between 1 to 20.

Python Sieve of Eratosthenes

Lets now implement Python Sieve of Eratosthenes

import math
def printPrime(num):
	l = list(range(2,num+1))
	for i in range(2,int(math.sqrt(num)+1)):
		for j in range (i*i, num+1, i):
			if j in l:
				l.remove(j)
	return l		
num = int(input("Enter the upper limit: "))
primeList = printPrime(num)
print(f"******* Prime numbers between 1 to {num} **********")
print(*primeList)

• We get the upper limit from the user and create a list ‘l’ using range() function.
• Then the iteration starts from 2 [since it is the smallest prime in the given list] till the square root of the number passed.
• Now using the inner loop we will remove the multiples of the current prime number, range (i*i, num+1, i).
  • For example, the current prime number is 2, then the inner loop will start with 4 and gets incremented by 2 for each iteration
• For each inner loop iteration, we will check if the list ‘l’ has the particular element or not, if it has, then removes that element as it is a multiple of the current prime.
• This loop continues and finally, we will have a list that consists of only the prime numbers.

Output:

Enter the upper limit: 44
******* Prime numbers between 1 to 44 **********
1 2 3 5 7 11 13 17 19 23 29 31 37 41 43