Python Program For Sieve Of Eratosthenes Algorithm

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:

1. For Loop

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

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.