Home » Python » Python programs

Find all Prime numbers less than or equal to N using the Sieve of Eratosthenes algorithm in Python

In this tutorial, we will learn how to find all Prime numbers less than or equal to N by using the Sieve of Eratosthenes algorithm in Python programming language?
Submitted by Bipin Kumar, on October 09, 2019

As we all know that the prime number is an integer greater than 1 which is only divisible by 1 or itself. For example 2,3,5,7,11,.. etc. The value of N is given by the user. Before going to solve this problem, we will learn a little bit about the Sieve of Eratosthenes and it's an algorithm.

What is the Sieve of Eratosthenes?

It is a simple and ancient method for finding all Prime numbers less than or equal to N.

Algorithm to find Prime numbers by Sieve of Eratosthenes

1. Initially, we will create a boolean array of size equal to the N and mark each position in the array True.
2. We initialize a variable p as 2. If the variable is prime then mark each multiple of number False in the array and update the variable p by increment.
3. Repeat step 2 until the square of the variable p is less than or equal to N.
4. Return, the elements in the array with True contains all Prime numbers.

Implementation of the above algorithm using python program

# input the value of N
N=int(input("Input the value of N: "))

Primes=[True for k in range(N+1)]
p=2
Primes[1]=False
Primes[0]=False

while(p*p<=N):
    if Primes[p]==True:
        for j in range(p*p,N+1,p):
            Primes[j]=False
    p+=1

for i in range(2,N):
    if Primes[i]:
        print(i,end=' ')

Output

Input the value of N: 50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47