Primzahl-Test: Ist n eine Primzahl?
Teste, ob eine ganze Zahl eine Primzahl ist – mit Trial Division. Bei zusammengesetzten Zahlen wird der kleinste Teiler ausgegeben.
Erklärung
Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und sich selbst ohne Rest teilbar ist. Die ersten Primzahlen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, … Die 2 ist die einzige gerade Primzahl. Trial Division ist die einfachste Methode: Man probiert alle Teiler von 2 bis √n durch. Findet man keinen, ist n prim. Der Trick mit √n: Hat n einen Teiler d > √n, dann gibt es zwangsläufig auch einen Teiler n/d < √n. Es reicht also, bis √n zu testen. Für kleine Zahlen ist Trial Division blitzschnell. Für sehr große Zahlen (Hunderte von Stellen) braucht man bessere Verfahren wie Miller-Rabin (probabilistisch), AKS (deterministisch, aber langsamer) oder ECPP. Die größte derzeit bekannte Primzahl (Mersenne-Primzahl 2^82589933 − 1) hat über 24 Millionen Stellen. Warum Primzahlen so wichtig sind: Sie sind die Grundbausteine der natürlichen Zahlen (Fundamentalsatz der Arithmetik – jede Zahl hat eine eindeutige Primfaktorzerlegung). In der modernen Welt sichern sie unsere Verschlüsselung: RSA basiert darauf, dass das Multiplizieren zweier großer Primzahlen einfach, das Faktorisieren des Produkts aber praktisch unmöglich ist. Online-Banking, HTTPS, digitale Signaturen – alles ruht auf Primzahlen. Vermutungen wie die Riemann-Hypothese oder die Goldbachsche Vermutung beschäftigen sich mit Verteilung und Eigenschaften der Primzahlen und gehören zu den größten ungelösten Problemen der Mathematik.
Häufige Fragen
Ist 1 eine Primzahl? +
Nein, per Definition. Sonst wäre die Primfaktorzerlegung nicht eindeutig (man könnte beliebig viele 1en multiplizieren).
Warum reicht das Testen bis √n? +
Wenn n = a · b und a > √n, muss b < √n sein. Findet man also keinen Teiler ≤ √n, gibt es auch keinen größeren.
Was sind Mersenne-Primzahlen? +
Primzahlen der Form 2^p − 1 (mit p ebenfalls prim). Sie liefern bisher die größten bekannten Primzahlen.
Wie viele Primzahlen gibt es? +
Unendlich viele – das hat schon Euklid bewiesen. Allerdings werden sie unter großen Zahlen seltener (Primzahlsatz: ungefähr n/ln(n) Primzahlen unter n).
Wozu Primzahlen in der Praxis? +
Kryptografie (RSA, Diffie-Hellman), Hashfunktionen, Pseudozufallszahlen-Generatoren, Fehlererkennende Codes.