Select Page

# Program for Sieve of Eratosthenes using Python

by | Aug 13, 2021 | Python Programs

Home » Python » Python Programs » Program for Sieve of Eratosthenes using Python

## Introduction

The task is to print all the prime numbers smaller than or equal to the given number n (given n must be small). ## Program

```def SOE(ip_num):
# Initialize all the element with True, the value will be False if p_num[val] is not prime
p_num = [True for val in range(ip_num + 1)]
i = 2
while (i * i <= ip_num):
# Check if num is prime
if (p_num[i] == True):
# Find multiples of prime number
for val in range(i * 2, ip_num + 1, i):
p_num[val] = False
i += 1
p_num= False
p_num= False

for i in range(ip_num + 1):
if p_num[i]:
# Print prime numbers
print(i)

ip_num = int(input("Enter the number: "))
print("The primes numbers smaller than equal to {0} are: ".format(ip_num ) )
SOE(ip_num)```

## Output ## Explanation

Approach:

1. List all the prime numbers from 2 to N.
 2 3 4 5 6 7 8 9 10

1. Find and mark all the numbers divisible by 2 and numbers greater or equal to its square.
 2 3 4 5 6 7 8 9 10

1. Move to next unmark number i.e. 3 and repeat the step 2.
 2 3 4 5 6 7 8 9 10

1. Repeat step 2 for all the unmarked numbers.
2. Stop when there are no more numbers to eliminate.
 2 3 4 5 6 7 8 9 10

1. Print all the unmarked numbers. These unmarked numbers are the prime numbers smaller than the given number.

Prime numbers:

 2 3 5 7 9

## Author

• A Full Stack Developer with 10+ years of experience in technical content creation.

• 