Sieve of Eratosthenes In Python

Let’s code the Sieve Of Eratosthenes algorithm for prime numbers using Python. We’ll be using Python 3.8.10. Let’s go! ⚡⚡✨✨

Eratosthenes was a mathematician that lived in Ancient Greece. The Sieve Of Eratosthenes is an algorithm he developed that allows us, even today, to efficiently find the prime numbers less than any integer n. Here is our code:

def esieve(n):
    multiples = []
    for i in range(2, n+1):
        if i not in multiples:
            print(i)
            for j in range(i*i, n+1, i):

                multiples.append(j)

esieve(17)

#Output
#2
#3
#5
#7
#11
#13
#17

Let’s explain what is happening here:

1. Our function esieve() is what will actually implement the Sieve of Eratosthenes algorithm. It takes one argument n and will print all of the prime numbers less than or equal to n. These are the steps:
   • we declare a new list multiples
   • we generate a list of integers from 2 to n+1
   • starting at i=2 we “mark” all the multiples of i in the list by inserting each multiple into our list multiples, up to n+1
   • every time we finish this loop we check to see if i is in the list multiples, if not, it is a prime number and we print it to the screen
   • then we increment to i=3 and run through all the numbers again, each time inserting multiples of i into our list multiples and checking to see if, after the loop is done, it is in the list multiples
   • we proceed by incrementing i in this manner and doing this “marking” until n+1 at which point the process is complete and the sieve has done its job
2. We modified the sieve to include primes up to and including n.

Simple right? There are far more fancy ways to do this but it is always good to practice and produce readable code. The other solutions look more elegant but they aren’t readable.

Find out more about this algorithm HERE. And check our another great tutorial HERE. Thanks for reading! Good luck! 👌👌👌