Primzahl-Prüfer (mit Primfaktorzerlegung)

Was eine Primzahl ist

Eine Primzahl ist eine natürliche Zahl größer als 1, die keine positiven Teiler außer 1 und sich selbst hat. Die ersten Primzahlen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. Sie sind die ‚Atome' der ganzzahligen Arithmetik – jede ganze Zahl ≥ 2 kann eindeutig als Produkt von Primzahlen geschrieben werden (Fundamentalsatz der Arithmetik).

1 ist per Konvention keine Primzahl. 0 und negative Zahlen sind keine Primzahlen. 2 ist die einzige gerade Primzahl – jede andere gerade Zahl ist durch 2 teilbar und damit zusammengesetzt.

Wie der Test funktioniert

Wir verwenden Probedivision: Überprüfe Teilbarkeit durch 2, dann 3, dann 5, 7, 11, … bis √n. Wenn keine glatt teilt, ist n eine Primzahl. Wir verwenden die 6k±1-Optimierung, die nur Kandidaten der Form 6k+1 oder 6k−1 prüft (da alle Primzahlen > 3 diese Form haben), was die Anzahl der Tests um 2/3 reduziert.

Probedivision ist schnell für n bis ~10^15 (Sekundenbereich). Darüber hinaus werden fortgeschrittene Tests wie Miller-Rabin (probabilistisch) oder AKS (deterministisch) benötigt. Wir begrenzen auf 10^18, um das Einfrieren des Browsers bei extremen Eingaben zu verhindern.

Warum Primzahlen wichtig sind

Kryptographie: RSA-Verschlüsselung multipliziert zwei ~1.000-stellige Primzahlen zu einer Zahl, die schwer zu faktorisieren ist. Die Sicherheit beruht auf der Schwierigkeit der Faktorisierung großer Zahlen – eine Herausforderung, die seit Jahrtausenden erforscht wird.

Mathematikunterricht: Primfaktorzerlegung ist grundlegend. Konzepte wie GCD, LCM, modulare Arithmetik, Brüche und Zahlentheorie bauen alle auf der Primfaktorstruktur auf.

Informatik: Hash-Tabellen-Größen, Zufallszahlengeneratoren und viele Algorithmen verwenden Primzahlen für ihre besonderen Teilbarkeitseigenschaften.