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:

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.

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:

• Python Variables
• Python Data Types
• Python print() Method
• Read input as an integer in Python
• Python int() Method
• Python input() Method
• Python Conditional Statements
• Python Loops

Python Basic Programs »