# Sieve of Eratosthenes | Python

## CodeCatch

### April 26th, 2021 04:42:20 PM

```					# Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.
# For example, if n is 10, the output should be “2, 3, 5, 7”. If n is 20, the output should be “2, 3, 5, 7, 11, 13, 17, 19”.

# Python program to print all primes smaller than or equal to
# n using Sieve of Eratosthenes

def SieveOfEratosthenes(n):

# Create a boolean array "prime[0..n]" and initialize
# all entries it as true. A value in prime[i] will
# finally be false if i is Not a prime, else true.
prime = [True for i in range(n + 1)]
p = 2
while (p * p <= n):

# If prime[p] is not changed, then it is a prime
if (prime[p] == True):

# Update all multiples of p
for i in range(p * 2, n + 1, p):
prime[i] = False
p += 1
prime= False
prime= False
# Print all prime numbers
for p in range(n + 1):
if prime[p]:
print (p)

# driver program
if __name__=='__main__':
n = 30
print("Following are the prime numbers smaller")
print("than or equal to ", n)
print("than or equal to ", n)
SieveOfEratosthenes(n)
```