# 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[0]= False

p_num[1]= 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)```

## 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 different domain including SAP, Blockchain, AI and Web Development.