Primzahl prüfen: Warum die Wurzel als Grenze genügt

Inhalt
Für die Frage, ob eine Zahl eine Primzahl ist, gibt es eine feste Rechenreihenfolge. Die 1 scheidet per Definition von vornherein aus, danach prüfen Sie zuerst die 2 und die 3, und für die übrigen Kandidaten genügt es, bis zur Quadratwurzel zu dividieren.
Wer die Logik eines Primzahltests verstehen oder eine bestimmte Zahl von Hand nachrechnen möchte, kommt in der Regel an genau dieser Reihenfolge ins Stocken.
Zusammenfassung ① Eine Primzahl ist „eine natürliche Zahl größer als 1, die nur die 1 und sich selbst als Teiler hat“. Deshalb ist die 1 per Definition ausgeschlossen. ② Sondern Sie zuerst die Vielfachen von 2 und 3 aus, bleiben nur noch Kandidaten übrig, die bei Division durch 6 den Rest 1 oder 5 lassen. ③ Gilt n = a × b, ist mindestens einer der Faktoren a und b kleiner oder gleich der Quadratwurzel von n. Es genügt daher, bis zur Quadratwurzel zu dividieren.
Wo es beim Prüfen auf Primzahlen hakt
Wenn Sie zwei- oder dreistellige Zahlen von Hand prüfen, stellt sich irgendwann die Frage, bis wohin Sie eigentlich dividieren müssen, bevor Sie aufhören dürfen.
Prüfen Sie zum Beispiel, ob 91 eine Primzahl ist: Weder durch 2 noch durch 3 lässt sich die Zahl ohne Rest teilen. Es liegt nahe, einfach mit 5, 7, 11, 13 … weiterzumachen. Ohne ein Abbruchkriterium dividieren Sie dann endlos weiter.
Auch beim Programmieren hakt es an derselben Stelle. Bei der Aufgabe „Schreibe eine Funktion, die prüft, ob n eine Primzahl ist“ taucht der Hinweis „Es genügt, bis zur Quadratwurzel zu teilen“ häufig auf. Wer aber nicht weiß, warum das reicht, schreibt den Code letztlich nur auswendig hin.
Kennt man nur die Lösung, aber nicht das Rechenprinzip, kann man schon bei etwas größeren Zahlen (fünf oder sechs Stellen) nicht mehr selbst überprüfen, ob das Ergebnis stimmt. Wenn Sie sich die Reihenfolge der Prüfschritte einmal sauber klargemacht haben, löst sich dieses Problem.
Primzahltest von Hand: die Rechenreihenfolge
Die folgende Reihenfolge entspricht der, die ein Primzahltest intern abarbeitet. Wenn Sie ihr folgen, können Sie bei jeder natürlichen Zahl auch von Hand feststellen, ob sie eine Primzahl ist.
Schritt 1 und 2: die 1 ausschließen, zuerst 2 und 3 prüfen
Die Definition lautet: Eine Primzahl ist eine natürliche Zahl größer als 1, die nur die 1 und sich selbst als Teiler hat. Die 1 hat nur einen einzigen Teiler, nämlich sich selbst (1), und erfüllt die Definition deshalb nicht. Sie scheidet von Anfang an aus. 2 und 3 sind selbst die kleinsten Primzahlen und gelten daher sofort als Primzahlen.
Schritt 3 und 4: Vielfache von 2 und 3 aussortieren und die Kandidaten eingrenzen
Ist die verbleibende Zahl ein Vielfaches von 2 (also gerade) oder von 3, steht sofort fest, dass sie keine Primzahl ist. Der Wert, durch den sie teilbar war (2 oder 3), wird als Teiler angezeigt. 51 etwa ist durch 3 teilbar und wird deshalb schon in diesem Schritt als zusammengesetzte Zahl erkannt.
Nachdem alle Vielfachen von 2 und 3 ausgeschlossen sind, bleiben nur Zahlen übrig, die bei Division durch 6 den Rest 1 oder 5 lassen (also von der Form 6k+1 oder 6k+5).
Beginnen Sie deshalb bei 5 und springen Sie in Sechserschritten weiter. Sie müssen dann nur jeweils zwei Kandidaten (i und i+2) testen, also 5, 7, 11, 13, 17, 19 und so fort. Alle übrigen Fälle brauchen Sie nicht zu prüfen.
Schritt 5: nur bis zur Quadratwurzel dividieren und dann aufhören
Ist n = a × b ohne Rest teilbar, dann ist mindestens einer der Faktoren a und b kleiner oder gleich √n. Wären nämlich beide größer als √n, läge ihr Produkt über n. Findet sich also bis √n kein Teiler, steht fest, dass die Zahl eine Primzahl ist.
91 und 97 selbst nachrechnen
91 ist weder ein Vielfaches von 2 noch von 3 und besteht damit Schritt 3. √91 beträgt etwa 9,54, als Kandidaten bleiben also nur 5 und 7.
Teilen Sie 91 durch 5, bleibt ein Rest. Durch 7 dagegen geht es auf: 91 = 7 × 13. Damit ist 91 eine zusammengesetzte Zahl, und 7 ist ein Teiler.
Und 97? Auch 97 ist kein Vielfaches von 2 oder 3, und √97 beträgt etwa 9,85. Als Kandidaten kommen also ebenfalls 5 und 7 infrage. Keiner der beiden teilt 97 ohne Rest. Weitere Prüfungen sind nicht nötig: 97 ist eine Primzahl.
Wenn Sie die Reihenfolge einmal von Hand durchgegangen sind, hilft es beim Verstehen, die gleiche Rechnung mit einem Werkzeug nachzuvollziehen, das sie sofort ausführt. Mit unserem Werkzeug „Primzahltest und Primzahlgenerator“ nachprüfen.
Kostenloses Tool: Geben Sie eine Zahl ein und sehen Sie sofort, ob sie eine Primzahl ist, samt Teiler. Für einen Bereich erzeugt es auch die Primzahlliste.

Typische Missverständnisse beim Lesen des Ergebnisses
Das Ergebnis eines Primzahltests ist eindeutig. Bei der Deutung der angezeigten Texte gibt es jedoch zwei Stellen, an denen leicht Missverständnisse entstehen.
Der als „Teiler“ angezeigte Wert ist nicht die Menge aller Teiler der Zahl, sondern der Wert, der im Lauf der Prüfung als Erstes ohne Rest aufging – also der kleinste Primfaktor. Die tatsächlichen Teiler von 91 sind 1, 7, 13 und 91, also vier Stück. Angezeigt wird aber nur die 7, die bei der Berechnung zuerst gefunden wurde.
Je größer die Zahl, desto mehr Kandidaten müssen bis √n geprüft werden. Bei einer siebenstelligen Zahl nahe 1 Million liegt √n bei etwa 1000. Selbst mit der Optimierung durch Sechserschritte müssen dann einige hundert Kandidaten geteilt werden, bis die Prüfung abgeschlossen ist. Ab dieser Größenordnung ist Nachrechnen von Hand praktisch unrealistisch.
| Angezeigter Text | Tatsächliche Bedeutung |
|---|---|
| „Keine Primzahl, Teiler: 7“ (am Beispiel 91) | Gemeint ist nicht die Menge aller Teiler von 91 (1, 7, 13, 91), sondern der kleinste Primfaktor 7 |
| „Primzahl“ | Außer der 1 und der Zahl selbst gab es bis √n keinen Wert, der ohne Rest aufging |
| Eingabe leer oder keine Zahl | Wird als NaN behandelt und als Fehler angezeigt |
Zusammenfassung
- Eine Primzahl ist eine natürliche Zahl größer als 1, die nur die 1 und sich selbst als Teiler hat. Die 1 mit nur einem Teiler ist per Definition ausgeschlossen.
- Prüfen Sie zuerst 2 und 3 und sondern Sie deren Vielfache aus, bleiben nur Kandidaten übrig, die bei Division durch 6 den Rest 1 oder 5 lassen.
- Gilt n = a × b, ist einer der Faktoren a und b mindestens kleiner oder gleich √n. Es genügt also, bis √n zu dividieren, um zu entscheiden, ob eine Primzahl vorliegt.
- Der angezeigte „Teiler“ ist nicht die Menge aller Teiler der Zahl, sondern der kleinste Primfaktor, der während der Rechnung zuerst gefunden wurde.
- Mit steigender Stellenzahl wächst auch die Zahl der zu prüfenden Kandidaten. Statt von Hand nachzurechnen, ist es daher zuverlässiger, den Primzahltest sofort mit dem Werkzeug durchzuführen.
Kostenloses Tool: Geben Sie eine Zahl ein und sehen Sie sofort, ob sie eine Primzahl ist, samt Teiler. Für einen Bereich erzeugt es auch die Primzahlliste.
Häufige Fragen
Warum ist die 1 keine Primzahl?
Eine Primzahl ist eine natürliche Zahl größer als 1, die nur die 1 und sich selbst als Teiler hat. Die 1 hat nur einen einzigen Teiler, nämlich sich selbst (1), und erfüllt diese Bedingung daher nicht. Deshalb gilt die 1 weder als Primzahl noch als zusammengesetzte Zahl, sondern als eigene Kategorie.
Sind die im Ergebnis genannten „Teiler“ alle Teiler der Zahl?
Nein. Angezeigt wird nur der eine Wert, der bei der Berechnung zuerst ohne Rest aufging, und das ist immer der kleinste Primfaktor der Zahl. 91 hat tatsächlich vier Teiler (1, 7, 13 und 91), angezeigt wird aber nur die 7.
Warum ist die 2 die einzige gerade Primzahl?
Jede gerade Zahl größer als 2 ist durch 2 teilbar. Sie hat damit drei oder mehr Teiler (1, 2 und sich selbst) und erfüllt die Bedingung für eine Primzahl nicht. Die 2 ist die einzige gerade Zahl, die nur zwei Teiler hat, nämlich 1 und 2, und bleibt deshalb eine Primzahl.
Wie wird die Primzahlliste erzeugt?
Verwendet wird das Sieb des Eratosthenes. Dabei werden alle Zahlen von 2 bis zur gewählten Obergrenze aufgeschrieben, die Vielfachen der Primzahlen der Reihe nach gestrichen, und nur die Zahlen, die am Ende übrig bleiben, sind Primzahlen.
Der zulässige Eingabebereich reicht bis maximal 1 Million. Größere Werte werden automatisch auf 1 Million begrenzt.
Dieser Artikel basiert auf unserem koreanischen Original. Koreanisches Original lesen