Loop Control Statements in C Introduction to HTML How to use the Github API The image tag, anchor tag and the button tag Ordered and Unordered Lists in HTML The division tag HTML Forms Tables in HTML Introduction to C Programming Introduction to Python Varibles and Datatypes in Python Operators in Python Typecasting in Python Input and Output in Python If Else in Python Loops in Python Break, Continue and Pass in Python Python practice section 1 Lists in Python Tuple 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.