from math import ceil
n=50
#Idee: Liste mit True/False ob die Zahlen 0,1,2,3,... Primzahlen sind
isPrime = [True for i in range(n+1)]

#Alle Zahlen ab 2 durchgehen, welche noch nicht durchgestrichen worden sind.
for i in range(2,n+1):
    #ist noch nicht rausgesrichen
    if isPrime[i] == True:
        #alle Vielflachen rausstreichen
        for j in range(2*i,n+1,i):
            isPrime[j] = False 
#alle nicht rausgesrichenen ausgeben
for p in range(2,n + 1): 
        if isPrime[p]: 
            print(p)

def Sieb(n):
    isPrime = [True for i in range(n+1)]
    
    for i in range(2,n+1):
        if isPrime[i] == True:
            for j in range(2*i,n+1,i):
                isPrime[j] = False 
    primes = []
    #alle nicht rausgesrichenen zur Liste hinzufügen
    for p in range(2,n + 1): 
            if isPrime[p]: 
                primes.append(p)
    return(primes)

print(Sieb(30))

#Eigentlich müsste nur bis Wurzel von n überprüft werden:
def SiebSchneller(n):
    isPrime = [True for i in range(n+1)]
    
    for i in range(2,int(ceil(sqrt(n)))):
        if isPrime[i] == True:
            for j in range(2*i,n+1,i):
                isPrime[j] = False 
    primes = []
    #alle nicht rausgesrichenen zur Liste hinzufügen
    for p in range(2,n + 1): 
            if isPrime[p]: 
                primes.append(p)
    return(primes)
print(SiebSchneller(30))