Sieve of Eratosthenes - Finding prime numbers less than a given number

In this tutorial, we will see how to find all the prime numbers less than a given number using Sieve of Eratosthenes algorithm.

Sieve of Eratosthenes is the most classic and efficient algorithms to find all the prime numbers up to a given limit. Say, you’re given a number ‘n’ and you’re asked to find all the prime numbers less than ‘n’, then how will you do that?

Sieve of Eratosthenes Algorithm

Take the list of all integers from 2 to n, i.e., [2,3,4,…,n]
Now, starting with i=2 in the list, mark all the multiples of 2 in the list as composite.
Assign the value of i to the next unmarked element in the list and repeat the above step.
Continue this procedure until all the elements in the list are processed.
At the end, the set of elements that have not been marked as composite are the prime numbers that are less than ‘n’.

At each step, the next unmarked number to which we assign the value of i is a prime number because it has not been divisible by any of the numbers that are less than that in the previous steps.

So, the set of unmarked numbers obtained at the end is the set of prime numbers that are less than ‘n’.

Dry run

Finding all the prime numbers that are less than 18 :

Taking the list of all integers from 2 to 18: [2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18]
i=2, marking all the multiples of 2 in the list as composite: [2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18]
The next unmarked element is 3, so take i as 3 now and mark all multiples of 3 as composite : [2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18]
The next unmarked element is 5, so, i=5 and all the multiples of 5 are already marked. Same goes with i=7,11,13,17.
So, the list of prime numbers that are less than 18 is 2,3,5,7,11,13,17.

Implementation in python

SieveOfEratosthenes.py

def SieveOfEratosthenes(n):

    prime = [True for i in range(n+1)]
    for i in range(2,n+1):
        if(prime[i] == True):
            j=2
            while i*j<=n :
                prime[i*j] = False
                j = j+1

    #printing all the prime numbers less than n
    for i in range(2,n+1):
        if(prime[i] == True):
            print (i, end=" ") 

    print()

if __name__ == "__main__":
    SieveOfEratosthenes(18)

Output

2 3 5 7 11 13 17

Optimizing the above implementation

If any integer n is composite, then n has a prime divisor less than or equal to √n. So, we can further reduce the number of steps and optimize the above implementation. For optimizing the above solution,

At each step, for the unmarked integer i, mark all the integers that are divisible by i and are greater than or equal to the square of it as composite.
Check for the next unmarked integer and assign it to i, until i<= √n.

The implementation in python after the above optimization:

SieveOfEratosthenes.py

import math

def SieveOfEratosthenes(n):

    prime = [True for i in range(n+1)]
    for i in range(2,(int)(math.sqrt(n))+1):
        if(prime[i] == True):
            j=i*i 
            while j<=n :
                prime[j] = False
                j = j+i 

    #printing all the prime numbers less than n
    for i in range(2,n+1):
        if(prime[i] == True):
            print (i, end=" ") 

    print()

if __name__ == "__main__":
    SieveOfEratosthenes(18)

Complexity analysis

The time complexity of this algorithm is O( n*log log n) and space complexity is O( n )

Finding all the prime numbers in a given range

To find all the prime numbers in a given range of [L,R], generate all the prime numbers up to √R using the above method. Then, use those primes to mark all the composite numbers in the range of [L,R]. The list of unmarked elements at the end is the set of prime numbers in the range of [L,R].

Putting it together

This algorithm is based on the simple idea that, if a number is prime, then none of the numbers less than that can divide it. So, we iterate over all the numbers from 2 to n and mark all the multiples of each number in the list as composite. The numbers that are left unmarked, are the ones that were not divisible by any integer. So, the list of unmarked numbers is the list of prime numbers that are less than n.

References:

Happy Learning 🙂