# Zahl, bis zu der alle Primzahlen bestimmt werden sollen:
x = 1000

import time

print()
print("Sieb des Eratosthenes")
print()
startzeit = time.time()

kandidat = [True for i in range(0, x + 1)]
# alternativ: kandidat = (x + 1) * [True]

anzahl_gefundener_primzahlen = 0
i = 2
while i <= x:
    if kandidat[i]:
        print(i, end=", ")
        anzahl_gefundener_primzahlen = anzahl_gefundener_primzahlen + 1
        if i * i <= x:         # Könnte diese Bedingung weglassen: bei x = 100 Millionen ohne sie: 67 Sekunden; mit ihr: 54 Sekunden.
            j = 2 * i
            while j <= x:
                kandidat[j] = False
                j = j + i
    i = i + 1
print()
print()
print(f'Anzahl der Primzahlen bis {x}: {anzahl_gefundener_primzahlen}')
print(f'Laufzeit: {time.time() - startzeit} Sekunden.')
print()
# Ca. 0.06 Sekunden bei x = 100000
# Ca. 10 Minuten 36 Sekunden bei x = 1 Milliarde