14.06.2021
Sieb des Eratosthenes
Das Sieb des Eratosthenes ist ein Algorithmus für die Anlegung einer Liste von Primzahlen bis zu einer gewählten Zahl.
Diese Implementation in Python kann die Zahlen 0 bis 100.000.000 innerhalb von 25 Sekunden durchlaufen und gibt dabei alle 5.761.455 Primzahlen aus.
import time
def sieb_des_eratosthenes(maximaler_wert: int) -> list[int]:
from math import isqrt
primzahlen = [True] * maximaler_wert
if maximaler_wert <= 2:
return [2]
primzahlen[0] = False
primzahlen[1] = False
for i in range(2, isqrt(maximaler_wert) + 1):
if primzahlen[i]:
for j in range(i * i, maximaler_wert, i):
primzahlen[j] = False
return [i for i in range(maximaler_wert) if primzahlen[i]]
start = time.time()
print(sieb_des_eratosthenes(1000000))
ende = time.time()
print('{:5.3f}s'.format(ende-start), end=' ')