Python-Übungen für Einsteiger

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.

  • Einsteiger
  • 2 Min. Lesezeit
  • 1 ausführbares Beispiel

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.

Von Fliesen-Rechtecken zum Code
number > 1🚪 Nur Zahlen über 1 können Primzahlen sein
divisor * divisor <= number🪞 Beim Quadrat aufhören: Danach kommen nur Wiederholungen
number % divisor == 0🔍 Ein volles Rechteck passt: keine Primzahl
divisor += 1➡️ Die nächste Breite ausprobieren
Wird bis zur Quadratwurzel kein Teiler gefunden, ist die Zahl prim.
In einem Satz

Eine Primzahl ist eine ganze Zahl größer als 1, deren einzige positive Teiler 1 und sie selbst sind.

Das Wichtigste

  1. is_prime = number > 1 beginnt für 0, 1 und negative Zahlen mit False, denn die sind nie prim.
  2. while divisor * divisor <= number and is_prime: hört an der Quadratwurzel auf oder sobald ein Teiler gefunden ist.
  3. number % divisor == 0 bedeutet, dass divisor die Zahl ohne Rest teilt.
  4. 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

Code ausführen →
main.py
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}")
Run-Button für dieses Beispiel erstellen

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.

  1. Ändere die Eingabedaten und sage das Ergebnis voraus, bevor du den Code ausführst.
  2. Füge eine Prüfung für leere oder ungültige Daten hinzu.
  3. Lagere die Logik in eine eigene Funktion aus und teste sie mit verschiedenen Datensätzen.
Im Python-Compiler ausführen →

Häufige Fehler

1 als Primzahl behandeln

1 hat nur einen Teiler, ist also nicht prim. Prüfe zuerst number > 1.

Problem
is_prime = True  # 1 would be reported as prime
Lösung
is_prime = number > 1

Bis zur Zahl selbst durchlaufen

Das liefert die richtige Antwort, probiert aber viel mehr Teiler als nötig.

Problem
for divisor in range(2, number):
Lösung
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.

Alle Challenges