ADVERTISEMENT
ADVERTISEMENT

Python program to find prime numbers using sieve of Eratosthenes

Here, we will take input from the user and print all prime numbers smaller than the given number.
Submitted by Shivang Yadav, on April 12, 2021

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.

A prime number is a natural number that is greater than 1 and cannot be formed by multiplying two smaller natural numbers.

Program to find prime number using the 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.

Example:

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.

sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

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.

Program to find prime numbers using the 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 »



ADVERTISEMENT



ADVERTISEMENT



Comments and Discussions


ADVERTISEMENT

ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.