Primzahlen in Python prüfen
In dieser Lektion prüfst du, ob eine Zahl eine Primzahl ist, indem du Teiler nur bis zu ihrer Quadratwurzel testest.
Einführung
Das Problem
Primzahlen stecken hinter der Verschlüsselung im Internet, hinter Hashtabellen und vielen Rätseln. Zu prüfen, ob eine Zahl prim ist, indem du jeden Teiler bis zur Zahl selbst ausprobierst, klappt bei 29, wird bei großen Zahlen aber quälend langsam. Eine kleine Einsicht macht die Prüfung viel schneller.
Stell es dir so vor
Teiler suchen ist wie Fliesen zu einem vollen Rechteck legen. 36 Fliesen passen als 1×36, 2×18, 3×12, 4×9 und 6×6. Nach dem Quadrat (6×6) kommen nur dieselben Rechtecke noch einmal, nur gedreht. Hinter der Quadratwurzel gibt es also nichts Neues zu finden. 29 Fliesen passen nur als 1×29, also ist 29 eine Primzahl.
number > 1🚪 Nur Zahlen über 1 können Primzahlen seindivisor * divisor <= number🪞 Beim Quadrat aufhören: Danach kommen nur Wiederholungennumber % divisor == 0🔍 Ein volles Rechteck passt: keine Primzahldivisor += 1➡️ Die nächste Breite ausprobierenEine Primzahl ist eine ganze Zahl größer als 1, deren einzige positive Teiler 1 und sie selbst sind.
Das Wichtigste
is_prime = number > 1beginnt für 0, 1 und negative Zahlen mit False, denn die sind nie prim.while divisor * divisor <= number and is_prime:hört an der Quadratwurzel auf oder sobald ein Teiler gefunden ist.number % divisor == 0bedeutet, dassdivisordie Zahl ohne Rest teilt.- Für 29 probiert die Schleife nur 2, 3, 4 und 5, bevor sie sagen kann, dass die Zahl prim ist.
Wann verwendet man das?
- Zahlenrätsel und Übungen, etwa Primzahlen auflisten oder Primfaktoren finden.
- Lernen, warum frühes Aufhören und Prüfen nur bis zu einer Grenze Schleifen schneller machen.
- Eingaben in Mathe-Werkzeugen prüfen.
Wann du es nicht brauchst
- Alle Primzahlen bis zu einer großen Grenze auflisten: Das Sieb des Eratosthenes ist viel schneller, als jede Zahl einzeln zu prüfen.
- Kryptografie mit Zahlen aus Hunderten Stellen: Echte Systeme nutzen probabilistische Tests.
Beispielcode
number = 29
is_prime = number > 1
divisor = 2
while divisor * divisor <= number and is_prime:
if number % divisor == 0:
is_prime = False
divisor += 1
print(f"{number} is prime: {is_prime}")
Ergebnis der Ausführung
29 is prime: True
Erklärung des Codes
Die Schleife muss Teiler nur testen, solange divisor * divisor <= number gilt. Der Grund: Hat n einen Teiler größer als die Quadratwurzel von n, gehört dazu immer ein kleinerer Teiler, den die Schleife schon geprüft hat. So sinkt die Komplexität auf O(√n), und das Ergebnis zeigt, dass 29 eine Primzahl ist.
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungen zur Vertiefung
Ändere den Code anhand der folgenden Vorschläge. Wenn du selbst etwas änderst und das Ergebnis beobachtest, verstehst du viel mehr, als wenn du den Code nur liest.
- Ändere die Eingabedaten und sage das Ergebnis voraus, bevor du den Code ausführst.
- Füge eine Prüfung für leere oder ungültige Daten hinzu.
- Lagere die Logik in eine eigene Funktion aus und teste sie mit verschiedenen Datensätzen.
Häufige Fehler
1 als Primzahl behandeln
1 hat nur einen Teiler, ist also nicht prim. Prüfe zuerst number > 1.
is_prime = True # 1 would be reported as prime
is_prime = number > 1
Bis zur Zahl selbst durchlaufen
Das liefert die richtige Antwort, probiert aber viel mehr Teiler als nötig.
for divisor in range(2, number):
while divisor * divisor <= number:
Lektion fertig?
Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.
Mit einer Challenge üben
Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.
- Primzahl-Prüfung Entscheide, ob eine Zahl eine Primzahl ist. Einfach
- Größter Primfaktor Finde die größte Primzahl, die einen positiven Integer teilt. Mittel
- Primzahlen mit einem Sieb auflisten Finde Primzahlen bis zu einem Grenzwert, indem zusammengesetzte Vielfache markiert werden. Mittel