➗Primzahltest

Was ist eine Primzahl?

Eine Primzahl ist eine ganze Zahl größer oder gleich 2, die außer 1 und sich selbst keine Teiler hat. Zahlen wie 2, 3, 5, 7 und 11 sind Primzahlen, und 2 ist die einzige gerade Primzahl.

Ist 1 eine Primzahl?

1 ist keine Primzahl. Primzahlen sind als ganze Zahlen ab 2 definiert, denn würde man 1 zu den Primzahlen zählen, gälte die Eigenschaft der Primfaktorzerlegung „jede ganze Zahl lässt sich auf genau eine Weise als Produkt von Primzahlen darstellen“ nicht mehr.

Wie man Primzahlen erkennt

Ob eine ganze Zahl n eine Primzahl ist, lässt sich feststellen, indem man sie nacheinander durch die Zahlen bis √n teilt: Ist sie durch keine davon teilbar, ist sie eine Primzahl. Zum Beispiel ist 91 durch 7 teilbar, das kleiner als √91 (etwa 9,5) ist, und daher keine Primzahl.

• Probedivision：Bei der Probedivision wird n nacheinander durch die Zahlen von 2 bis √n geteilt, um Teiler zu finden. Bei vielen Stellen wird die Anzahl der Divisionen enorm groß.
• Miller-Rabin-Test：Der Miller-Rabin-Test verwendet mehrere Zahlen als „Basen“, untersucht die Reste von Potenzen und sucht so nach einem Beweis, dass eine Zahl keine Primzahl ist. Damit lassen sich auch große Zahlen in kurzer Zeit prüfen.