Introduction to Python Programming Cycle of Python Varibles and Datatypes in Python Input and Output in Python Operators in Python Precedence of Operators in Python Typecasting in Python If Else in Python Loops in Python Break, Continue and Pass in Python Functions in Python Default Arguments and Keyword Arguments in Python Strings in python Lists in Python Tuple in Python Dictionary in Python Sets in Python List Comprehension in Python Unpacking Sequences in Python Higher Order Functions in Python Lambda Functions in Python Sieve of Eratosthenes Algorithm in Python Linear Search in Python Binary Search in Python Selection Sort in Python Bubble Sort in Python Insertion Sort in Python Merge Sort in Python

Sieve of Eratosthenes Algorithm in Python

Sieve of Eratosthenes is an algorithm used to find all prime numbers from 1 up to a given range. In this article, we will take a look at the naive method as well as the sieve method along with their time complexities.

The Naive approach

We will take every number from 2 to n and check whether it's prime or not since we already know that 1 is not prime. We know that the highest factor of a number n is √n. So,to check whether a given number is prime or not, we will run an inner loop from i = 1 to i = √n, and check whether n is divisible by any i. If yes, then n is not prime since we have found a factor of n. Otherwise, n is a prime number. The code for doing this is given below - 

import math
n=int(input("Enter range : "))
for i in range(2,n+1):
    prime=True
    for j in range(2,int(math.sqrt(i))+1):
        if i%j==0:
            prime=False
            break
    if prime==True:
        print(i,end=" ")
Output
Enter range : 50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Time Complexity : O(n√n)
Explanation : We run an outer loop for all numbers from 1 to n. Inside it, there is an inner loop that runs from 1 to sqrt(n) to check the prime condition. So, the time Complexity will be O(n√n).
Space Complexity : O(1) no additional space used.

The Sieve approach

We will take a list of size n with index i representing whether the ith number is prime or not. True represents that the number is prime and false represents that the number is non-prime. Initially, we will assume that all numbers are prime, so the list contains True at every index. We know that 0 and 1 are not prime, so we will mark them False in the beginning and start the iteration from i = 2. For every number from i = 2 to i = n, if the ith value is true that means that the ith number is prime, so we will mark all its multiples False and move to the next iteration. In the end, we will use this list to find the numbers that are prime.
Dry Run
  1. In the beginning, all numbers from 2 to n are prime. 0 and 1 are not prime.
  2. At i=2, 2 is prime. So, all its multiples i.e. 4, 6, 8, ..., 48, 50 will be marked non-prime.
  3. At i=3, 3 is prime. So, all its multiples i.e. 3,6,9,...,45,48 will be marked non-prime.
  4. At i=4, 4 is not prime.
  5. At i=5, 5 is prime. So, all its multiples i.e. 5,10,15,...,45,50 will be marked non-prime.
  6. Similarly, for all i till n.
The code for doing this is given below.

n=int(input("Enter range : "))

is_prime=[True for i in range(0,n+1)]
is_prime[0]=False
is_prime[1]=False

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

for i in range(2,len(is_prime)+1):
    if is_prime[i]==True:
        print(i,end=" ")
Output
Enter range: 50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Time Complexity : O(nlog(logn))
Explanation : The outer loop runs (n-1) times from i=2 to n.The inner loop runs for all prime numbers i.e For j=2, it runs n/2 times since there are n/2 multiples of 2 till n. Similarly for j=3, it runs n/3 times. For j=5, (n/5) times, For j=7, (n/7) times, for all i till n. So, the total number of times the inner loop runs will be:
= (n/2) + (n/3) + (n/5) + (n/7) + (n/11) + (n/13) + . . . + (n/n)
= n ( 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + 1/13 + . . . + 1)
On solving the series, we get log(log(n))
Hence, the overall complexity of the sieve algorithm becomes O(nlog(logn)).
Space Complexity : O(n) space used by the list for storing whether a number is prime or not.