Primzahl-Prüfer
Prüfe, ob eine Zahl eine Primzahl ist, und finde ihren kleinsten Teiler.
Ergebnis
Ergebnis
Primzahl
Kleinster Teiler
97
So funktioniert's
Eine Primzahl hat genau zwei Teiler: eins und sich selbst. Zwei, drei, fünf, sieben, elf — und zwei ist die einzige gerade Primzahl, denn jede andere gerade Zahl ist durch zwei teilbar. Die Eins ist bewusst ausgeschlossen. Sie hat nur einen Teiler, und sie zuzulassen würde den Fundamentalsatz der Arithmetik zerstören, nach dem jede ganze Zahl über eins auf genau eine Weise in Primfaktoren zerfällt. Mit erlaubter Eins könnte 6 sein 2×3 oder 1×2×3 oder 1×1×2×3, und die Eindeutigkeit bräche zusammen. Primzahlen sind die Atome der ganzen Zahlen, und sie werden seltener, ohne je auszugehen — Euklid bewies, dass es unendlich viele gibt. Ihre Schwierigkeit ist heute Infrastruktur: Moderne Verschlüsselung ruht darauf, dass das Multiplizieren zweier großer Primzahlen leicht ist, das Zurückgewinnen aus dem Produkt aber, soweit bekannt, nicht.
Anzeige
Häufige Fragen
Ist 1 eine Primzahl?
Nein — eine Primzahl braucht genau zwei verschiedene Teiler, 1 hat nur einen.
Was ist die kleinste Primzahl?
2 — und die einzige gerade Primzahl.
Wie weit muss ich Teiler testen?
Nur bis zur Quadratwurzel der Zahl. Hat n einen Teiler größer als √n, muss es einen passenden kleineren geben — findet man unter der Wurzel keinen, ist die Zahl prim. Diese einzige Einsicht macht Primzahltests praktikabel.
Anzeige