Sieve of Eratosthenes python
#The other code in Grepper(By Disgusted Donkey) is in python2
#this one is python3
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
# put all prime numbers in a list
r = []
for p in range(n + 1):
if prime[p]:
r.append(p)
#return the list
return r
# driver program
if __name__=='__main__':
n = 50
print ("Following are the prime numbers smaller")
print ("than or equal to", n)
print(SieveOfEratosthenes(n))