Primzahlrechner: Primzahltest, nächste Primzahl und Primzahllisten

So benutzt du den Primzahlrechner

Wähle oben, was du wissen möchtest, und gib die Zahl ein. Beim Primzahltest erfährst du nicht nur ja oder nein, sondern bei zusammengesetzten Zahlen auch einen Teiler und die vollständige Zerlegung. Im Erweitert-Bereich kannst du das Sieb des Eratosthenes für die Zahlen bis 100 einblenden.

Was ist eine Primzahl?

Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und durch sich selbst teilbar ist. Die ersten sind 2, 3, 5, 7, 11, 13, 17, 19, 23 und 29. Die 2 ist die einzige gerade Primzahl. Alle anderen Zahlen ab 4 heißen zusammengesetzt, weil sie sich als Produkt kleinerer Zahlen schreiben lassen. Schon Euklid bewies um 300 v. Chr., dass es unendlich viele Primzahlen gibt.

Wie prüft man, ob eine Zahl prim ist?

Für kleine Zahlen reicht es, alle Primzahlen bis zur Wurzel der Zahl als Teiler auszuprobieren. Hat eine Zahl nämlich einen Teiler über der Wurzel, gehört zu ihm ein zweiter unter der Wurzel. Für 2027 genügen die Primzahlen bis 45. Keine davon teilt 2027, also ist 2027 eine Primzahl.

Bei sehr großen Zahlen wäre das viel zu langsam. Der Rechner nutzt deshalb den Miller-Rabin-Test, der auf einem Satz von Fermat beruht. Er erkennt zusammengesetzte Zahlen zuverlässig, auch Zahlen wie 561, die einfachere Tests täuschen. Für Zahlen bis 3,3 · 10²⁴ ist sein Ergebnis mit den verwendeten Testbasen beweisbar richtig.

Das Sieb des Eratosthenes

Um alle Primzahlen bis zu einer Grenze zu finden, schreibt man alle Zahlen auf und streicht nacheinander die Vielfachen von 2, 3, 5, 7 und so weiter. Was übrig bleibt, sind die Primzahlen. Das Verfahren geht auf Eratosthenes von Kyrene zurück, der im 3. Jahrhundert v. Chr. auch den Erdumfang erstaunlich genau bestimmte. Bis 100 gibt es 25 Primzahlen, bis 1000 sind es 168 und bis eine Million 78 498.

Häufige Fragen