You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
29 lines
881 B
29 lines
881 B
import time
|
|
|
|
def sieve_of_eratosthenes(limit):
|
|
# Erzeuge eine Liste, die angibt, ob eine Zahl eine Primzahl ist
|
|
is_prime = [True] * (limit + 1)
|
|
p = 2
|
|
|
|
while (p * p <= limit):
|
|
# Wenn is_prime[p] nicht verändert wurde, ist p eine Primzahl
|
|
if is_prime[p]:
|
|
# Aktualisiere alle Vielfachen von p als nicht prim
|
|
for i in range(p * p, limit + 1, p):
|
|
is_prime[i] = False
|
|
p += 1
|
|
|
|
# Sammle alle Primzahlen
|
|
prime_numbers = [p for p in range(2, limit + 1) if is_prime[p]]
|
|
return prime_numbers
|
|
|
|
# Beispielverwendung: Finde alle Primzahlen bis 100
|
|
limit = 10000
|
|
start_time = time.ticks_ms()
|
|
prime_numbers = sieve_of_eratosthenes(limit)
|
|
end_time = time.ticks_ms()
|
|
|
|
running_time =time.ticks_diff(end_time,start_time)
|
|
|
|
print(f'Primzahlen bis {limit}: {prime_numbers}')
|
|
print(f'Laufzeit: {running_time}ms')
|
|
|