Home » Python » Python Programs

Python Program for Sieve of Eratosthenes

Python | Sieve of Eratosthenes Implementation: Here, we will learn how to find the prime numbers using Sieve of Eratosthenes in Python? By Shivang Yadav Last updated : April 14, 2023

Python programming language is a high-level and object-oriented programming language. Python is an easy to learn, powerful high-level programming language. It has a simple but effective approach to object-oriented programming.

Sieve of Eratosthenes

Sieve of Eratosthenes is an ancient algorithm of finding prime numbers for any given range. It's actually about maintaining a Boolean table to check for corresponding prime number.

Sieve of Eratosthenes Algorithm

• Get input from user for value N.
• Create a boolean array of size N+1, prime[N+1] and assign all values to TRUE.
• 0 and 1 is not prime, Thus prime[0] = prime[1] = FALSE.
• Loop from 2 to root(N) with variable i.
  • if prime[i] == TRUE -> all multiple of i in array are made false.
• Loop for the array, and print all values 'p', for which prime[p] is TRUE.

Implementation for finding prime numbers using sieve of eratosthenes

We will take a positive integer as input from the user and then return all prime numbers smaller than or equal to the given number.

Sample Input/Output

Input:
n = 25

Output: 
2, 3, 5, 7, 11, 13, 17, 19, 23

To find prime numbers smaller than or equal to the given number. We will loop till the number and for each value check weather it is a prime number or not.

But here, we will find prime numbers using the sieve of Eratosthenes.

Python program to find prime numbers using sieve of Eratosthenes

# Python program to find prime numbers 
# using sieve of Eratosthenes

import math

# Getting input from user 
n = int(input("Enter the number : "))

# finding all prime numbers 
prime = [True for i in range(n + 1)]
prime[0] = prime[1] = False
i = 2

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

# Printing all prime numbers...
print("All prime numbers smaller than the number are ")
for p in range(n + 1):
    if prime[p]:
        print (p, end = " ")

Output

Enter the number : 54
All prime numbers smaller than the number are
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53

Python Basic Programs »

---