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.
234
567
8910

 

  1. Find and mark all the numbers divisible by 2 and numbers greater or equal to its square.
234
567
8910

 

  1. Move to next unmark number i.e. 3 and repeat the step 2.
234
567
8910

 

  1. Repeat step 2 for all the unmarked numbers.
  2. Stop when there are no more numbers to eliminate.
234
567
8910

 

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

Prime numbers:

23 
5 7
 9 

 

 

Leave a comment

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