In this tutorial, you will learn to write a Python Program For the Sieve Of Eratosthenes Algorithm.
A prime number is a positive integer greater than 1 that has no positive integer divisors other than 1 and itself.
In other words, a prime number is a number that is only divisible by 1 and itself.
Examples of prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and so on.
To understand this program you should have an understanding of the following topics:
Python Program For Sieve Of Eratosthenes Algorithm
n = int(input("Enter a number: "))
sieve = [True] * (n+1)
sieve[0] = False
sieve[1] = False
for i in range(2, int(n**0.5)+1):
if sieve[i]:
for j in range(i*i, n+1, i):
sieve[j] = False
if sieve[n]:
print(n, "is a prime number")
else:
print(n, "is not a prime number")
Output
Enter a number: 59
59 is a prime number
In this program, we first create a list called sieve with n+1 elements, all initially set to True.
We then set the first two elements (sieve[0] and sieve[1]) to False, since 0 and 1 are not prime.
We then loop through all the numbers from 2 to the square root of n, checking if each number is prime (i.e., if sieve[i] is True).
If it is, we mark all its multiples as not prime by setting sieve[j] to False, where j is a multiple of i.
Finally, we check whether n is prime by checking the value of sieve[n].
If it is True, we print that n is a prime number.
Otherwise, we print that n is not a prime number.
Discover more from Python Mania
Subscribe to get the latest posts sent to your email.