Primzahlprüfer

Den Primzahlprüfer verwenden

1. Einen Modus wählen: Der Tab Zahl prüfen testet eine einzelne ganze Zahl auf Primalität; der Tab Primzahlen bis N finden listet jede Primzahl unterhalb einer von dir gewählten Obergrenze auf.
2. Die Zahl eingeben. Der Prüf-Modus akzeptiert jede positive ganze Zahl bis zu 2⁵³-1; der Sieb-Modus akzeptiert bis zu zehn Millionen, damit die Benutzeroberfläche reaktionsfähig bleibt.
3. Abschicken mit Enter oder der Schaltfläche. Im Prüf-Modus erhältst du ein Ja/Nein-Ergebnis und, wenn die Zahl zusammengesetzt ist, ihre Primfaktorisierung. Im Sieb-Modus erhältst du die vollständige Liste plus die Anzahl der gefundenen Primzahlen.
4. Die Faktorisierung durchsehen, um zu sehen, welche kleinen Primzahlen deine Zahl teilen; das ist oft nützlicher als die Ja/Nein-Antwort.
5. Die Liste kopieren mit der Schaltfläche "Alle kopieren"; die Ausgabe ist kommagetrennt und lässt sich sauber in eine Tabellenkalkulation oder ein Code-Snippet einfügen.

Im Inneren: Probedivision und das Sieb

Für eine einzelne Prüfung verwendet das Tool rad-basierte Probedivision: es teilt zuerst durch 2 und 3, dann durch Zahlen der Form 6k±1 bis zu √n. Das eliminiert Vielfache von 2 und 3 aus der Kandidatenliste und liefert eine ca. dreifache Beschleunigung gegenüber der normalen Probedivision. Der Algorithmus ist deterministisch und korrekt für jede Eingabe, die in eine JavaScript-Zahl passt.

Für das Sieb implementiert das Tool das Sieb des Eratosthenes in einem Uint8Array der Größe N+1 Bytes. Es markiert 0 und 1 als zusammengesetzt, und für jede gefundene Primzahl p beginnt es, Vielfache von p² zu streichen (frühere Vielfache wurden bereits von kleineren Primzahlen gestrichen). Das läuft in O(N log log N) Zeit und O(N) Raum. Für sehr großes N würde ein segmentiertes Sieb oder der probabilistische Miller-Rabin-Test besser skalieren, aber Probedivision und klassisches Eratosthenes sind genau richtig für den Bereich, den dieses Tool unterstützt.

Wann du einen Primzahltest brauchst

• Einen Primmodulus verifizieren, wenn man ein Diffie-Hellman-Demo für einen Kryptographie-Kurs von Hand aufbaut.
• Eine Liste von Primzahlen für ein Project-Euler-Problem oder eine Programmierwettbewerbs-Lösung generieren.
• Die Primfaktorisierung eines Produkts finden, um einen Bruch zu kuerzen oder eine Quadratwurzel zu vereinfachen.
• Das Sieb als erste Begegnung mit algorithmischem Denken in einem Informatik-Kurs lehren.
• Prüfen, ob eine Hash-Tabellen-Größe prim ist, eine verbreitete Daumenregel beim Hash-Funktions-Design.
• Die nächste Primzahl über einem Zielwert finden, nützlich für Load-Balancing-Gewichte, die koprim sein müssen.

Sonderfälle, die das Tool behandelt

• 1 ist keine Primzahl. Die Definition erfordert genau zwei verschiedene positive Teiler; 1 hat nur sich selbst. Das Überspringen dieser Konvention bricht den Fundamentalsatz der Arithmetik, weil die eindeutige Faktorisierung versagen würde.
• 2 ist die einzige gerade Primzahl. Jede andere gerade Zahl ist durch 2 teilbar, sodass das Sieb sie in seinem ersten Durchlauf streicht.
• Carmichael-Zahlen wie 561 und 1105 täuschen naive Fermat-Tests, werden aber hier korrekt als zusammengesetzt identifiziert, weil die Probedivision ihre kleinen Faktoren direkt findet.
• Große Mersenne-nahe Zahlen sind für dieses Tool kein Sonderfall; 2³¹-1 (2.147.483.647) ist prim und die Probedivision bestätigt es in Millisekunden.
• Eingaben über 2⁵³-1 verlieren die ganzzahlige Präzision in JavaScripts number; dafür ist ein BigInt-basierter Miller-Rabin, nicht dieses Tool, die richtige Wahl.
• Null oder negative Eingaben werden auf UI-Ebene abgelehnt; Primalität ist nur für natürliche Zahlen größer als 1 definiert.

Primzahlen, kurz erklärt

Primzahlen sind die multiplikativen Atome der ganzen Zahlen: Jede positive ganze Zahl größer als 1 faktorisiert sich eindeutig als Produkt von Primzahlen (der Fundamentalsatz der Arithmetik, von Euklid in den Elementen bewiesen). Es gibt unendlich viele, wie Euklid mit seinem berühmten Widerspruchsargument zeigte. Ihre Verteilung ist im Detail unregelmäßig, aber im Durchschnitt glatt: Die Primzahlzählfunktion π(N) ist asymptotisch zu N/ln(N), ein Ergebnis, das 1896 unabhängig von Hadamard und de la Vallée Poussin bewiesen und Primzahlsatz genannt wurde. Wilsons Theorem liefert eine saubere, aber unpraktische Charakterisierung: p ist genau dann prim, wenn (p-1)! ≡ -1 (mod p). Für Primzahltests sind die modernen Arbeitspferde Miller-Rabin (probabilistisch, extrem schnell) und AKS (deterministisch polynomial-zeitlich, 2002 angekündigt), die beide bei den Skalen, auf die dieses Tool abzielt, nicht benötigt werden.

Wann man nach etwas Leistungsfähigerem greifen sollte

Für Primzahlen jenseits von zehn Millionen werden segmentierte Siebe, die in C (primesieve) oder Python mit numpy-Vektorisierung implementiert sind, einen Browser-Sieb um zwei Größenordnungen schlagen. Für Primzahltests für Zahlen mit Hunderten von Stellen - die Skala, die für die RSA-Schlüssel-Generierung wichtig ist - benötigst du Miller-Rabin mit einem kuratierten Satz von Zeugen, den OpenSSL und GMP einsatzbereit mitliefern. Für schnelle Faktorisierung von 20 bis 60-stelligen zusammengesetzten Zahlen sind Pollards Rho und die elliptische Kurvenmethode (ECM) in Tools wie YAFU oder Msieve das Richtige. Dieses Browser-Tool ist die richtige Wahl, wenn du ohne Installation eine schnelle Antwort für eine Zahl bis ca. 10¹⁵ benötigst, und es gewinnt bei null Installationsaufwand jedes Mal.