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