Primzahltest und Primfaktorzerlegung

So prüfen Sie, ob eine Zahl eine Primzahl ist

1. Geben Sie eine Ganze Zahl ein. Auch Ausdrücke werden akzeptiert: 2^61-1, 10^12+39, 20!+1 oder 3711.
2. Die Antwort erscheint schon beim Tippen; klicken Sie auf Prüfen, um der Zerlegung einer schwierigen Zahl mehr Zeit zu geben.
3. Lesen Sie das Ergebnis, die Primfaktorzerlegung, die Anzahl der Teiler, die Vorherige Primzahl und die Nächste Primzahl. Der Bereich Begründung erklärt, wie die Antwort zustande kam, und Zerlegung kopieren kopiert das Produkt der Primfaktoren.
4. Um Primzahlen aufzulisten, füllen Sie unter Primzahlen in einem Bereich die Felder Von und Bis aus und klicken auf Primzahlen auflisten.

Zahlen bis 2048 Bit (etwa 617 Stellen) werden akzeptiert, und alles läuft in Ihrem Browser.

Was ist eine Primzahl?

Eine Primzahl ist eine ganze Zahl größer als 1, deren einzige Teiler 1 und sie selbst sind: 2, 3, 5, 7, 11, 13 … Eine Zahl mit weiteren Teilern heißt zusammengesetzt, und sie lässt sich auf genau eine Weise als Produkt von Primzahlen schreiben – ihre Primfaktorzerlegung (360 = 2³ × 3² × 5). Die Zahlen 0 und 1 sind weder prim noch zusammengesetzt, und 2 ist die einzige gerade Primzahl.

Die Anzahl der Teiler ergibt sich aus der Zerlegung: Addieren Sie zu jedem Exponenten 1 und multiplizieren Sie. 360 = 2³ × 3² × 5 hat (3 + 1)(2 + 1)(1 + 1) = 24 Teiler. Eine Primzahl hat immer genau 2.

So funktioniert der Test

• Kleine Zahlen (unter einer Million) werden per Probedivision geprüft: Teilt keine Primzahl bis zur Quadratwurzel die Zahl, ist sie prim. Weiter muss man nicht gehen, denn eine zusammengesetzte Zahl hat immer einen Faktor, der nicht größer als ihre Quadratwurzel ist.
• Größere Zahlen werden zuerst durch jede Primzahl unter 1000 geteilt und dann dem Miller-Rabin-Test unterzogen. Mit den 13 Basen 2, 3, 5, …, 41 ist dieser Test nachweislich exakt für jede Zahl unter 3,3 × 10²⁴, darunter alle 64-Bit-Ganzzahlen. Für diese Zahlen ist die Antwort sicher.
• Oberhalb von 3,3 × 10²⁴ werden 25 Basen verwendet, und eine Zahl, die alle besteht, wird als wahrscheinliche Primzahl gemeldet. Die Fehlerwahrscheinlichkeit liegt unter 1 zu 10¹⁵, ein mathematischer Beweis ist das aber nicht. Fällt die Zahl durch den Test, ist sie mit Sicherheit zusammengesetzt.

So werden Zahlen zerlegt

Kleine Faktoren werden per Probedivision gefunden. Größere zusammengesetzte Teile werden mit dem Pollard-Rho-Algorithmus (Variante nach Brent) zerlegt, der Faktoren bis etwa 10 Stellen in Sekundenbruchteilen findet. Schwierigere Zahlen, etwa das Produkt zweier Primzahlen mit 15 oder mehr Stellen, können weit länger dauern als jedes Zeitlimit, daher bricht die Zerlegung nach einigen Sekunden ab. Der letzte Faktor wird dann als zusammengesetzt, aber nicht zerlegt markiert; ein erneuter Klick auf Prüfen gibt ihm mehr Zeit.

Primzahlen in einem Bereich

Die Bereichsliste verwendet ein segmentiertes Sieb des Eratosthenes, das die Vielfachen jeder Primzahl streicht. Es akzeptiert bis zu 1.000.000 Zahlen pro Bereich mit einer Obergrenze bis 10¹². Die Anzahl bezieht sich auf den ganzen Bereich, aufgelistet werden die ersten 2.000 Primzahlen. Zwischen 1 und 100 gibt es zum Beispiel 25 Primzahlen, unter einer Million 78.498.