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? By Bipin Kumar Last updated : January 05, 2024

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

Algorithm to find Prime numbers by Sieve of Eratosthenes is:

Initially, we will create a boolean array of size equal to the N and mark each position in the array True.
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.
Repeat step 2 until the square of the variable p is less than or equal to N.
Return, the elements in the array with True contains all Prime numbers.

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

# 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

The output of the above example is:

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

RUN 2:
Input the value of N: 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

To understand the above program, you should have the basic knowledge of the following Python topics: