Die Ergebnisse verstehen
Die folgende Tabelle zeigt die drei Ausgaben für einige Beispieleingaben.
| Eingabe | Prim? | Zerlegung | Nächste Primzahl |
|---|---|---|---|
| 97 | Ja | 97 | 101 |
| 84 | Nein | 2 x 2 x 3 x 7 | 89 |
| 100 | Nein | 2 x 2 x 5 x 5 | 101 |
| 2 | Ja (einzige gerade Primzahl) | 2 | 3 |
| 1 | Nein (weder prim noch zusammengesetzt) | - | 2 |
- Die 1 ist keine Primzahl: Primzahlen müssen genau zwei verschiedene Teiler besitzen, die 1 hat jedoch nur einen. Ihr Ausschluss erhält die Eindeutigkeit der Primfaktorzerlegung.
- Die Probedivision ist exakt, wird bei sehr großen Eingaben aber langsam; dieser Rechner akzeptiert Zahlen bis 10^12, wobei die Suche Teiler bis eine Million prüft.
- Die Suche nach der nächsten Primzahl endet in diesem Bereich garantiert rasch: Nach dem bertrandschen Postulat liegt zwischen n und 2n stets eine Primzahl.
Was ist eine Primzahl?
Eine Primzahl ist eine natürliche Zahl größer als 1, die genau zwei positive Teiler besitzt: 1 und sich selbst. Die ersten Primzahlen lauten 2, 3, 5, 7, 11, 13, 17, 19, 23 und 29. Die 2 ist die einzige gerade Primzahl, da jede andere gerade Zahl durch 2 teilbar ist. Zahlen größer als 1, die nicht prim sind, heißen zusammengesetzt; die 1 ist definitionsgemäß weder prim noch zusammengesetzt.
Der Fundamentalsatz der Arithmetik besagt, dass sich jede ganze Zahl größer als 1 bis auf die Reihenfolge der Faktoren auf genau eine Weise als Produkt von Primzahlen schreiben lässt. Wegen dieser eindeutigen Primfaktorzerlegung gelten Primzahlen als die Bausteine der ganzen Zahlen: 84 = 2^2 x 3 x 7, und keine andere Kombination von Primzahlen ergibt multipliziert 84.
Es gibt unendlich viele Primzahlen — ein Ergebnis, das Euklid um 300 v. Chr. bewies —, und sie werden mit wachsender Größe seltener, ohne dabei einem einfachen Muster zu folgen. Große Primzahlen bilden die Grundlage moderner Public-Key-Kryptografie (etwa RSA), die auf der praktischen Schwierigkeit beruht, das Produkt zweier sehr großer Primzahlen zu faktorisieren.
So verwenden Sie diesen Primzahlrechner
- Geben Sie eine ganze Zahl n von mindestens 1 ein. Dezimalzahlen werden auf die nächstkleinere ganze Zahl abgerundet.
- Lesen Sie das Primzahlurteil ab: Ein Häkchen bedeutet, dass die Zahl prim ist, ein Kreuz, dass sie zusammengesetzt ist (oder 1, was keines von beidem ist).
- Lesen Sie die Primfaktorzerlegung ab — das eindeutige Produkt von Primzahlen, das Ihre Zahl ergibt. Bei einer primen Eingabe ist die Zerlegung die Zahl selbst.
- Lesen Sie die nächste Primzahl ab, also die kleinste Primzahl, die echt größer als Ihre Zahl ist.
So wird auf Primalität geprüft: die Probedivision
Eine Zahl n ist genau dann zusammengesetzt, wenn sie einen Teiler größer als 1 und höchstens gleich der Quadratwurzel aus n besitzt. Der Grund: Teiler treten paarweise auf — gilt n = a x b mit a <= b, so folgt a <= √n. Die Probedivision muss daher nur Teilerkandidaten bis √n prüfen; nach der 2 genügen dabei die ungeraden Kandidaten.
Rechenbeispiel (prim): n = 97. Die Quadratwurzel aus 97 beträgt rund 9,85, daher genügt es, 2, 3, 5, 7 und 9 zu prüfen. 97 ist ungerade; 9 + 7 = 16 ist nicht durch 3 teilbar; die Zahl endet weder auf 0 noch auf 5; 97 / 7 = 13,857...; und 97 / 9 geht nicht auf. Es existiert kein Teiler, folglich ist 97 prim.
Rechenbeispiel (Zerlegung): n = 84. Dividieren Sie die Primzahlen der Reihe nach heraus: 84 / 2 = 42, 42 / 2 = 21, 21 / 3 = 7, und 7 ist prim. Somit gilt 84 = 2 x 2 x 3 x 7 = 2^2 x 3 x 7. Die nächste Primzahl nach 84 ist 89 (85 = 5 x 17, 86 = 2 x 43, 87 = 3 x 29, 88 = 2^3 x 11).
Häufige Fehler
- Die 1 als Primzahl zählen — definitionsgemäß besitzt eine Primzahl genau zwei verschiedene Teiler, die 1 aber nur einen.
- Annehmen, alle Primzahlen seien ungerade: Die 2 ist prim und zugleich die einzige gerade Primzahl.
- Teiler bis n prüfen, statt bei √n abzubrechen — jede zusammengesetzte Zahl besitzt einen Faktor bei oder unterhalb ihrer Quadratwurzel.
- Glauben, alle ungeraden Zahlen seien prim: 9 = 3 x 3, 15 = 3 x 5 und 21 = 3 x 7 sind ungerade und zusammengesetzt.
- Die Primfaktorzerlegung mit einer beliebigen Zerlegung verwechseln: 84 = 4 x 21 ist eine Zerlegung, die Primfaktorzerlegung lautet jedoch 2 x 2 x 3 x 7.
Häufig gestellte Fragen
Wie prüfe ich, ob eine Zahl prim ist?
Prüfen Sie, ob eine ganze Zahl von 2 bis zur Quadratwurzel der Zahl diese ohne Rest teilt. Tut es keine, so ist die Zahl prim. Für 97 beträgt die Quadratwurzel rund 9,85, und keine der Zahlen 2, 3, 5, 7 oder 9 teilt 97 — also ist 97 prim. Da Teiler stets paarweise auftreten, besitzt jede zusammengesetzte Zahl einen Faktor bei oder unterhalb ihrer Quadratwurzel.
Warum ist 1 keine Primzahl?
Eine Primzahl ist definiert als Zahl mit genau zwei verschiedenen positiven Teilern, nämlich 1 und sich selbst; die 1 besitzt jedoch nur einen Teiler. Die Definition schützt zudem den Fundamentalsatz der Arithmetik: Wäre 1 prim, so wären Zerlegungen nicht mehr eindeutig (6 = 2 x 3 = 1 x 2 x 3 = 1 x 1 x 2 x 3 und so fort).
Was ist eine Primfaktorzerlegung?
Sie ist die Darstellung einer Zahl als Produkt von Primzahlen, die nach dem Fundamentalsatz der Arithmetik bis auf die Reihenfolge eindeutig ist. So gilt etwa 84 = 2 x 2 x 3 x 7. Um sie zu finden, dividieren Sie fortlaufend die kleinste aufgehende Primzahl heraus, bis der verbleibende Quotient 1 oder prim ist.
Ist 2 eine Primzahl?
Ja — 2 ist prim, da ihre einzigen Teiler 1 und 2 sind, und sie ist die einzige gerade Primzahl. Jede andere gerade Zahl ist durch 2 teilbar und damit zusammengesetzt. Deshalb behandeln Primalitätstests die 2 gesondert und prüfen anschließend nur noch ungerade Kandidaten.
Wie viele Primzahlen gibt es?
Unendlich viele, wie Euklid um 300 v. Chr. bewies: Multipliziert man alle Primzahlen einer beliebigen endlichen Liste und addiert 1, so ist die entstehende Zahl durch keine von ihnen teilbar, es fehlt also eine Primzahl in der Liste. Primzahlen werden mit wachsender Größe seltener — nach dem Primzahlsatz beträgt ihre Dichte in der Nähe von n etwa 1 / ln(n) —, aber sie hören nie auf.
Warum sind Primzahlen in der Kryptografie wichtig?
Public-Key-Verfahren wie RSA beruhen auf einer Asymmetrie: Zwei große Primzahlen zu multiplizieren ist leicht, doch sie aus ihrem Produkt zurückzugewinnen, ist bei den praktisch verwendeten Größenordnungen (Hunderte von Stellen) rechnerisch sehr aufwendig. Sicherheitsschlüssel werden aus solchen Produkten gebildet, weshalb Primzahlerzeugung und Primalitätstests zu den zentralen kryptografischen Operationen zählen.
Quellenangaben
- Weisstein, Eric W. "Prime Number" and "Fundamental Theorem of Arithmetic." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. Oxford University Press (primes, unique factorization, Bertrand's postulate).
- Euclid. Elements, Book IX, Proposition 20 (infinitude of primes).