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

VeröffentlichtToolPrimzahltest und Primzahlgenerator

Inhalt
  1. Wo es beim Prüfen auf Primzahlen hakt
  2. Primzahltest von Hand: die Rechenreihenfolge
  3. Typische Missverständnisse beim Lesen des Ergebnisses
  4. Zusammenfassung
  5. Häufige Fragen

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.

Primzahltest und Primzahlgenerator

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 TextTatsä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 ZahlWird 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.
Primzahltest und Primzahlgenerator

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

Ähnliche Artikel

  1. Wechseldiskont berechnen: Diskontzinsen und AuszahlungsbetragSo berechnen Sie den Diskont eines Wechsels und den Auszahlungsbetrag: Formel, Rechenbeispiel und der Einfluss von 365/360 Tagen und Diskontbeginn.
  2. Verhältnisgleichung lösen: Außenglieder und InnengliederWie das Produkt der Außenglieder dem der Innenglieder entspricht, je nach Lage der Unbekannten X, und wie Sie die Aufgabe Schritt für Schritt von Hand lösen.
  3. Pyeong in Quadratmeter umrechnen: Warum 32 Pyeong 84 m² sindWarum 84 m² Nutzfläche als 32 Pyeong gelten, wie sich 1 Pyeong = 3,3058 m² ergibt und worin sich Liefer- und Nutzfläche unterscheiden – mit Rechenbeispielen.
  4. Satz des Pythagoras berechnen: Hypotenuse in 3 SchrittenSo berechnen Sie mit a²+b²=c² die Hypotenuse und die Katheten: quadrieren, addieren, Wurzel ziehen. Mit Beispielen, typischen Fehlern und Fällen ohne Lösung.
  5. Quadratische Gleichung lösen: Diskriminante und LösungsformelSo lösen Sie ax² + bx + c = 0: Mit dem Vorzeichen der Diskriminante D = b² − 4ac die Lösungsart bestimmen und Koeffizienten Schritt für Schritt einsetzen.
  6. Mietrendite berechnen: Cap Rate und EigenkapitalrenditeCap Rate und Eigenkapitalrendite (CoC) im Vergleich: Woher NOI, Zinsen und Eigenkapital kommen und was Kaufnebenkosten in der Rechnung ausmachen.

Passende Tools