from math import sqrt

#Sieve of Erastothenes for finding prime numbers
def sieve(maxnum) :
    # fill a list of numbers 1, 2, 3,....
    primes = []
    for i in range(maxnum) :
        primes.append(i)
    print(primes)

    # for each number that is still in list, knock out all its multiples
    for num in range(2, maxnum) :
        if primes[num] != 0 :
            print("knocking out multiples of", num)
            for i in range(num*2, maxnum, num) :
                primes[i] = 0
                print("->", i)

    # print the remaining numbers
    print("All primes less than", maxnum)
    for num in primes :
        if num!=0 :
            print(num)

        
#Sieve of Erastothenes for finding prime numbers
def sieve2(maxnum) :
    # fill a list of numbers 1, 2, 3,....
    primes = []
    for i in range(maxnum) :
        primes.append(i)
    print(primes)

    # for each number that is still in list, knock out all its multiples
    for num in range(2, int(sqrt(maxnum))+1) :
        if primes[num] != 0 :
            print("multiples of", num, end=": ")
            for i in range(num*num, maxnum, num) :
                primes[i] = 0
                print(i, end=" ")
            print()

    # print the remaining numbers
    print("\nAll primes less than ", maxnum, ":", sep="")
    for i in primes :
        if i!=0 :
            print(i, end=" ")
    print()
        

sieve(30)