Python Program to Find Prime Numbers in a Range using Sieve of Eratosthenes


This is a Python Program to print prime numbers in a range using Sieve of Eratosthenes.

Problem Description

The program takes a range and prints prime numbers in that range using Sieve of Eratosthenes.

Problem Solution

1. Take the value of n from the user.
2. Initialise the sieve with numbers from 2 to n.
3. Use a while loop with the condition that the sieve is not empty
4. Get the smallest number that is prime
5. Remove that number and it’s multiples
6. Continue till the sieve is empty
7. Exit

Program/Source Code

Here is the source code of the Python Program to takes a range and print prime numbers in that range using Sieve of Eratosthenes. The program output is also shown below.

n=int(input("Enter upper limit of range: "))
while sieve:
Program Explanation

1. User must first enter the value for upper limit of range and store it in a variable n.
2. The sieve is initialised to a set which ranges from 2 to n( as n+1 is not included).
3. The while loop is used to ensure that the sieve isn’t empty.
4. The variable prime is initialised with the least number in the sieve and the prime number is printed.
5. The sieve is then removed with all multiples of the prime number.
6. Steps 4 and 5 continue till value of sieve becomes empty.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
Runtime Test Cases
Case 1:
Enter upper limit of range: 10
2	3	5	7	
Case 2:
Enter upper limit of range: 15
2	3	5	7	11	13

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.