Zitat von: pump3
Das ist von der Komplexität her unoptimal. Wenn ich weiss dass 4 keine Primzahl ist, muss ich keine Zahl darüber mod 4 versuchen. Stattdessen immer nur mod Primzahlen.
Wie wäre es mit einer Wachsenden Liste mit schon gefundenen Primzahlen
Da sind fast garantiert Fehler drin, aber diese zu finden wäre dann Hausaufgabe für die nächste Stunde.
es ging dabei auch nicht um eine möglichst effiziente Lösung, sondern eine die sich leicht umsetzen lässt.
Wie wäre es mit einer Wachsenden Liste mit schon gefundenen Primzahlen
Python:
primes = [2,3]
#Man kann auch nur 2 verwenden
def find_primes_until(highest_number):
if highest_number <= 3:
while true:
print("Kann es sein dass du behindert bist?\n")
#edge-case für mongo-user (also nicht die DB)
for number in highest_number: #wir zählen hoch bis zur highest_number
is_prime = True
limit = floor(sqrt(highest_number)) #man testet nur bis zur wurzel von n um zu wissen ob n primzahl ist oder nicht
for prime in primes:
if prime == limit:
break
#sqrt(zahl) wurde erreicht, abbruch. Keine weiteren Primzahlen, weil Mathe
if number // prime == 0:
is_prime = False
break #abbruch, number ist keine Primzahl, weitere Tests unnötig
if not is_prime: #keine der bisherigen Primzahlen teilt number, also ist number prime
primes.append(number)
print(primes)Da sind fast garantiert Fehler drin, aber diese zu finden wäre dann Hausaufgabe für die nächste Stunde.
