How to find all Prime numbers less than or equal to N by sieve of Eratosthenes in Python.

In this tutorial, We will see How to find all Prime numbers less than or equal to N by Sieve of Eratosthenes in Python. As we all know the definition, Prime numbers is a whole number greater than 1 whose factors are only one and itself. So, To solve this problem, we have to understand what is Sieve of Eratosthenes and it’s the algorithm.

What is the Sieve of Eratosthenes?

It is a simple and ancient method for finding all prime numbers up to any given limit.

Algorithm to find Prime numbers by Sieve of Eratosthenes:

  1. We create a boolean array of size equal to the given number (n) and mark each position in the array True.
  2. We initialize a variable as 2. If the variable is prime then mark each multiple of number False in the array and update the variable by increment.
  3. Repeat step 2 until the square of the variable is less than the given number(n).
  4. The elements in the array with True contains all Prime numbers less than or equal to the given number and print the elements of the array which is our Prime number.

Python program to find all Prime numbers less than or equal to N by Sieve of Eratosthenes

So, let’s start to understand the simple Python code.

Python program:

n=100
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:

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

So Guy’s, I hope you find it really useful.

You may also read:

Leave a Reply