🔢 Primzahl-Rechner

Eine Primzahl ist eine natürliche Zahl größer als 1, die genau zwei Teiler hat: die 1 und sich selbst. Lässt sich eine Zahl dagegen noch durch weitere Zahlen ohne Rest teilen, nennt man sie zusammengesetzte Zahl. Die ersten Primzahlen lauten 2, 3, 5, 7, 11, 13, 17, 19, 23 und 29.

Ein Sonderfall ist die 2: Sie ist die kleinste Primzahl und zugleich die einzige gerade — jede andere gerade Zahl ist schon durch 2 teilbar und damit zusammengesetzt. Die 1 zählt bewusst nicht als Primzahl, weil sie nur einen einzigen Teiler besitzt. Auch die 0 und negative Zahlen sind keine Primzahlen. Primzahlen gelten als die Grundbausteine der Zahlen: Aus ihnen lässt sich jede größere natürliche Zahl durch Multiplikation zusammensetzen. Der Rechner prüft jede eingegebene Zahl auf Teilbarkeit und nennt im Ergebnis den kleinsten gefundenen Teiler — oder bestätigt, dass keiner existiert und die Zahl somit prim ist.

Die Primfaktorzerlegung zerlegt eine Zahl in ein Produkt aus lauter Primzahlen. Man teilt dazu fortlaufend durch den jeweils kleinsten Primteiler, bis am Ende nur noch eine Primzahl übrig bleibt. Mehrfach auftretende Faktoren fasst man als Potenz zusammen: 360 = 2 × 2 × 2 × 3 × 3 × 5 schreibt man kompakt als 2³ × 3² × 5.

Der Hauptsatz der Arithmetik (auch Fundamentalsatz genannt) garantiert dabei etwas Bemerkenswertes: Jede natürliche Zahl größer als 1 hat genau eine Primfaktorzerlegung — bis auf die Reihenfolge der Faktoren. Es gibt also keinen zweiten Weg, 360 in Primzahlen zu zerlegen. Diese Eindeutigkeit ist der Grund, warum Primzahlen als die „Atome" der Zahlen gelten. Praktisch nutzt man die Zerlegung, um den größten gemeinsamen Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) zu bestimmen, um Brüche zu kürzen — und in der Kryptographie, wo das Zerlegen sehr großer Zahlen bewusst extrem aufwendig ist.

Will man nicht eine einzelne Zahl prüfen, sondern alle Primzahlen bis zu einer Obergrenze auflisten, ist das Sieb des Eratosthenes das klassische Verfahren. Es stammt aus der Antike (um 240 v. Chr.) und ist bis heute eines der effizientesten einfachen Verfahren der Primzahlsuche.

Die Idee ist ein systematisches Ausstreichen: Man schreibt alle Zahlen von 2 bis zur Obergrenze auf. Die kleinste noch nicht gestrichene Zahl ist prim — man behält sie und streicht alle ihre Vielfachen, da diese zusammengesetzt sein müssen. Mit 2 beginnend fallen so alle geraden Zahlen weg, danach mit der 3 deren Vielfache, dann mit der 5 und so weiter. Sobald die nächste Primzahl größer als die Wurzel der Obergrenze ist, kann man aufhören: Alle dann noch übrigen Zahlen sind garantiert prim. Genau dieses Sieb nutzt der Rechner im Modus „Primzahlen im Bereich".