Primzahltest und Primfaktorzerlegung

So funktioniert es

1. Wählen Sie einen Modus: eine Zahl prüfen, sie zerlegen, die Primzahlen bis N auflisten oder die benachbarten Primzahlen finden.
2. Geben Sie die Zahl ein — Punkte als Tausendertrennzeichen werden akzeptiert und ignoriert.
3. Das Ergebnis erscheint mit den Divisionen, die dahinterstecken. Alles wird in Ihrem Browser berechnet.

Über dieses Tool

Eine Primzahl hat genau zwei Teiler: 1 und sich selbst. Damit sind Primzahlen die Bausteine der Arithmetik: Jede ganze Zahl über 1 ist auf genau eine Weise ein Produkt von Primzahlen — das besagt der Fundamentalsatz der Arithmetik. 360 ist 2³ × 3² × 5 und nichts anderes; 91 sieht prim aus, ist in Wahrheit aber 7 × 13; 97 ist tatsächlich prim. Ist die Zerlegung erst bekannt, ergeben sich weitere Fakten von selbst — die Anzahl der Teiler ist das Produkt aus jedem Exponenten plus eins, 360 hat also (3 + 1) × (2 + 1) × (1 + 1) = 24 davon.

Der Primzahltest läuft hier über Probedivision, aber nur bis zur Quadratwurzel der Zahl und nur gegen Kandidaten der Form 6k ± 1, da alles andere ohnehin ein Vielfaches von 2 oder 3 ist. Das erspart zwei Drittel der Arbeit und klärt eine Zahl unter einer Billion in ein paar hunderttausend Divisionen, also in wenigen Millisekunden. Oberhalb von 10¹² wird selbst das im Browser langsam, deshalb wechselt die Antwort zum deterministischen Miller-Rabin-Test mit den Basen 2 bis 37, der für jede Zahl unter 3,3×10²⁴ nachweislich exakt ist — und damit für alles, was dieses Tool akzeptiert, bis 2⁵³ − 1. Für das Auflisten von Primzahlen kommt ein anderer Klassiker zum Einsatz: Das Sieb des Eratosthenes schreibt jede Zahl bis N auf, behält die kleinste nicht markierte, streicht alle ihre Vielfachen und wiederholt das, bis nur noch Primzahlen übrig sind.

Die Primfaktorzerlegung ist die Mechanik hinter dem Kürzen von Brüchen, dem Bestimmen von kgV und ggT und dem Vereinfachen von Quadratwurzeln — deshalb wird sie früh unterrichtet. Über die Schule hinaus beruht die RSA-Verschlüsselung genau auf der Schwierigkeit, große Zahlen zu zerlegen: Zwei große Primzahlen zu multiplizieren geht sofort, das rückgängig zu machen nicht, und diese Lücke ist das gesamte Sicherheitsargument. Primzahlen werden mit wachsenden Zahlen außerdem vorhersagbar seltener, gehen aber nie aus — das hat Euklid vor mehr als zweitausend Jahren bewiesen. Zahlen bis 2⁵³ − 1 lassen sich hier testen, Zerlegung und benachbarte Primzahlen funktionieren bis zu einer Billion, und die Primzahlliste reicht bis 100.000. Nichts von dem, was Sie eingeben, verlässt Ihren Browser.

Die Formel

Primzahltest per Probedivision: n ist prim, wenn keine ganze Zahl von 2 bis √n sie teilt, und es genügt, 2, 3 und danach jeden Kandidaten der Form 6k ± 1 zu prüfen. Die Zerlegung nutzt dieselben Divisionen und hält fest, wie oft jede Primzahl hineinpasst; die Anzahl der Teiler ist das Produkt aus jedem Exponenten plus eins. Die Primzahlliste verwendet das Sieb des Eratosthenes. Oberhalb von 10^12 stammt die Antwort vom deterministischen Miller-Rabin-Test mit den Basen 2 bis 37, exakt für jede Zahl unter 2^53.

Häufig gestellte Fragen