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.
30 lines
881 B
30 lines
881 B
2 months ago
|
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')
|