Program for Sieve of Eratosthenes using Python

Introduction

The task is to print all the prime numbers smaller than or equal to the given number n (given n must be small).

Program for Sieve of Eratosthenes using Python 

Program

def SOE(ip_num):

# Initialize all the element with True, the value will be False if p_num[val] is not prime

    p_num = [True for val in range(ip_num + 1)]

    i = 2

    while (i * i <= ip_num):

# Check if num is prime

        if (p_num[i] == True):

# Find multiples of prime number

            for val in range(i * 2, ip_num + 1, i):

                p_num[val] = False

        i += 1

    p_num[0]= False

    p_num[1]= False




    for i in range(ip_num + 1):

        if p_num[i]:

# Print prime numbers

            print(i)




ip_num = int(input("Enter the number: "))

print("The primes numbers smaller than equal to {0} are: ".format(ip_num ) )

SOE(ip_num)

Output

Program for Sieve of Eratosthenes using Python Output

Explanation

Approach:

  1. List all the prime numbers from 2 to N.
2 3 4
5 6 7
8 9 10

 

  1. Find and mark all the numbers divisible by 2 and numbers greater or equal to its square.
2 3 4
5 6 7
8 9 10

 

  1. Move to next unmark number i.e. 3 and repeat the step 2.
2 3 4
5 6 7
8 9 10

 

  1. Repeat step 2 for all the unmarked numbers.
  2. Stop when there are no more numbers to eliminate.
2 3 4
5 6 7
8 9 10

 

  1. Print all the unmarked numbers. These unmarked numbers are the prime numbers smaller than the given number.

Prime numbers:

2 3  
5   7
  9  

 

 

Author

  • Barry Allen

    A Full Stack Developer with 10+ years of experience in different domain including SAP, Blockchain, AI and Web Development.

    View all posts

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.