Q:

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

mahmoud2506
Save to bookmark
|
2022-05-19
|
  395 
0

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.
Python programming, examples, Python programming examples,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-19
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now