Primzahlen sind die Bausteine, aus denen sich jede natürliche Zahl zusammensetzt. Sie wirken auf den ersten Blick wie eine reine Schulbuchkuriosität, stecken aber heute in jeder verschlüsselten Verbindung, in Hashverfahren und in Zufallsgeneratoren. Dieser Ratgeber erklärt dir, was eine Primzahl genau ausmacht, wie du sie selbst überprüfst und warum sie in der Mathematik eine derart zentrale Rolle spielen.
Was ist eine Primzahl?
Eine Primzahl ist eine natürliche Zahl größer als 1, die genau zwei Teiler hat: die 1 und sich selbst. Die Zahl 7 ist prim, weil sie sich nur durch 1 und 7 ohne Rest teilen lässt. Die Zahl 8 dagegen ist zusammengesetzt, denn sie hat zusätzlich die Teiler 2 und 4.
Wichtig: Die 1 ist keine Primzahl. Sie hat nur einen einzigen Teiler und würde die Eindeutigkeit der Primfaktorzerlegung zerstören. Die kleinste und einzige gerade Primzahl ist die 2 – alle anderen geraden Zahlen sind durch 2 teilbar und damit zusammengesetzt. Wenn du schnell wissen willst, ob eine konkrete Zahl prim ist, übernimmt der Primzahl-Check die Prüfung und listet dir zusätzlich die Faktoren und die nächsten Primzahlen auf.
Die ersten Primzahlen
Die Reihe beginnt mit 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 und so weiter. Auffällig ist, dass die Abstände zwischen den Primzahlen unregelmäßig sind. Mal liegen zwei Primzahlen direkt nebeneinander (sogenannte Primzahlzwillinge wie 11 und 13), mal klaffen große Lücken. Der Primzahlsatz beschreibt zwar, wie dicht Primzahlen im Durchschnitt auftreten, eine einfache Formel zur direkten Berechnung der n-ten Primzahl existiert jedoch nicht.
Wie prüft man, ob eine Zahl prim ist?
Probedivision
Die anschaulichste Methode ist die Probedivision: Du teilst die Zahl der Reihe nach durch alle möglichen Teiler. Findest du keinen Teiler außer 1 und der Zahl selbst, ist sie prim. Ein praktischer Trick spart dabei enorm viel Arbeit: Du musst nur bis zur Quadratwurzel der Zahl testen. Hätte eine Zahl nämlich einen Teiler größer als ihre Wurzel, müsste es zwangsläufig auch einen kleineren geben.
Um 97 zu prüfen, reicht es also, die Teiler bis 9 (denn 9² = 81, 10² = 100) durchzugehen. Keine der Zahlen 2, 3, 5 und 7 teilt 97 – also ist 97 prim.
Sieb des Eratosthenes
Willst du alle Primzahlen bis zu einer Grenze finden, ist das Sieb des Eratosthenes das klassische Verfahren. Du schreibst alle Zahlen von 2 bis zur Obergrenze auf und streichst dann systematisch alle Vielfachen jeder gefundenen Primzahl. Was übrig bleibt, sind die Primzahlen. Dieses über 2000 Jahre alte Verfahren ist bis heute eine der effizientesten Methoden für kleine bis mittlere Zahlenbereiche.
Primfaktorzerlegung
Der Fundamentalsatz der Arithmetik besagt: Jede natürliche Zahl größer als 1 lässt sich auf genau eine Weise als Produkt von Primzahlen schreiben. So ist 60 = 2 × 2 × 3 × 5, kurz 2² × 3 × 5. Diese Eindeutigkeit macht Primzahlen zu den „Atomen" der Zahlenwelt – jede zusammengesetzte Zahl ist nichts anderes als ein Produkt von Primfaktoren.
Die Primfaktorzerlegung ist nicht nur Theorie. Du brauchst sie, um den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache zu bestimmen, Brüche zu kürzen oder Wurzeln zu vereinfachen. Wenn du mit ganzzahligen Teilern weiterarbeiten möchtest, helfen dir Werkzeuge wie der GGT KGV Rechner oder die gesamte Sammlung im Webtools-Bereich.
Warum Primzahlen so wichtig sind
Der praktische Wert der Primzahlen liegt in einer einfachen Asymmetrie: Zwei große Primzahlen miteinander zu multiplizieren ist trivial, das Produkt aber wieder in seine Faktoren zu zerlegen ist extrem aufwendig. Genau darauf baut das RSA-Verfahren auf, das jahrzehntelang das Rückgrat verschlüsselter Internetkommunikation war. Ein Schlüssel besteht aus dem Produkt zweier Primzahlen mit hunderten von Stellen – niemand kann diese in vertretbarer Zeit zurückrechnen.
Auch in Hashfunktionen, Prüfziffernverfahren und Pseudozufallsgeneratoren tauchen Primzahlen immer wieder auf, weil ihre Verteilung möglichst gleichmäßige und kollisionsarme Ergebnisse liefert.
Häufige Fragen
Ist 1 eine Primzahl?
Nein. Eine Primzahl muss genau zwei verschiedene Teiler haben. Die 1 hat nur einen einzigen Teiler und gilt deshalb per Definition nicht als prim.
Gibt es unendlich viele Primzahlen?
Ja. Bereits Euklid bewies vor über 2000 Jahren mit einem eleganten Widerspruchsbeweis, dass es keine größte Primzahl gibt – die Folge der Primzahlen reißt nie ab.
Wie finde ich schnell heraus, ob eine große Zahl prim ist?
Für überschaubare Zahlen genügt die Probedivision bis zur Quadratwurzel. Der Primzahl-Check nimmt dir diese Rechnung ab und zeigt bei zusammengesetzten Zahlen direkt die Faktoren. Für sehr große Zahlen mit hunderten Stellen kommen probabilistische Tests wie der Miller-Rabin-Test zum Einsatz.