Primzahlen prüfen und auflisten

So wird gerechnet

Eine Primzahl ist eine natürliche Zahl mit genau zwei verschiedenen Teilern: der 1 und sich selbst. An drei Zahlen entscheidet sich, ob die Definition stimmt: Die 0 ist keine Primzahl, weil sie von jeder Zahl ungleich 0 geteilt wird und damit mehr als zwei Teiler hat. Die 1 ist keine Primzahl, weil sie nur einen einzigen Teiler hat. Die 2 ist die kleinste Primzahl und die einzige gerade, weil jede andere gerade Zahl auch durch 2 teilbar ist und damit einen dritten Teiler hätte. Die Zahlen 0 und 1 sind danach weder prim noch zusammengesetzt.

Der Primzahltest arbeitet mit Probedivision: Der Rechner probiert nacheinander, ob 2 oder 3 die eingegebene Zahl teilt, und danach die Kandidaten des Sechserrasters, also 5 und 7, dann 11 und 13, dann 17 und 19 und so weiter, denn jede Zahl, die weder an einer 2er- noch an einer 3er-Position des Rasters liegt, kann nur noch an diesen beiden Positionen stehen. Abgebrochen wird an der Wurzel der Zahl. Der Grund: Wäre die Zahl das Produkt zweier Faktoren, die beide größer als ihre Wurzel sind, wäre das Produkt größer als die Zahl selbst, was unmöglich ist. Es genügt deshalb, bis zur Wurzel zu prüfen; findet sich dort kein Teiler, ist die Zahl beweisbar prim. Der Rechner rechnet dabei durchgehend mit ganzen Zahlen und vergleicht das Quadrat des Kandidaten mit der Zahl, statt eine Wurzel zu ziehen, denn eine gerundete Wurzel würde genau an der Obergrenze des Eingabebereichs falsch abbrechen können.

Zur Primfaktorzerlegung führt derselbe Durchgang gleich alles mit aus: Sobald ein Teiler gefunden ist, wird er so oft abgeteilt, bis es nicht mehr geht, und der nächste Kandidat folgt. Die Faktoren stehen am Ende aufsteigend, für 91 also 7 × 13, für 4 also 2 × 2. Der kleinste gefundene Teiler einer zusammengesetzten Zahl ist dabei immer eine Primzahl, weil alle kleineren Kandidaten die Probe schon verfehlt haben. Eine Primzahl ist ihre eigene Faktorisierung.

Rechenbeispiel

Ist 91 eine Primzahl?

Die Zahl 91 sieht auf den ersten Blick prim aus, denn sie liegt zwischen den bekannten Primzahlen 89 und 97. Die Probedivision findet aber schon früh einen Teiler: 91 geteilt durch 7 ergibt 13, also ist 91 = 7 × 13. Der Rechner nennt als kleinsten Teiler die 7, zeigt die Zerlegung 7 × 13 und die Tabelle mit den beiden Primfaktoren und ihren Exponenten; 91 ist damit keine Primzahl. Beispiel im Rechner öffnen.

Primzahlen von 1 bis 100

Im Bereich von 1 bis 100 liegen 25 Primzahlen. Die kleinste ist die 2, die größte die 97, ihre Summe ist 1.060. Die Zahlen 0 und 1 zählen nicht mit, weil sie keine Primzahlen sind; der Rechner beginnt die Liste deshalb von selbst bei der 2. Beispiel im Rechner öffnen.

Primzahlen bis 100

Die 25 Primzahlen bis 100 sind: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 und 97.

Die 2 ist die einzige gerade Zahl in der Liste, denn jede weitere gerade Zahl ist durch 2 teilbar. Die Abstände zwischen den Primzahlen werden nach oben im Durchschnitt größer, aber nie regelmäßig: Im Bereich von 200 bis 210 liegt zum Beispiel gar keine Primzahl, während die 101 und die 103 unmittelbar aufeinander folgen. Wer eine eigene Liste braucht, wählt im Rechner den Aufgabentyp „Primzahlen in einem Bereich“.

Was der Rechner nicht beantwortet

Zahlen über eine Billion (1.000.000.000.000) nimmt das Eingabefeld nicht an. Der Grund ist die Laufzeit der Probedivision: Sie prüft Teiler bis zur Wurzel der Zahl, bei einer Billion sind das rund eine Million Kandidaten, die das Sechserraster auf etwa ein Drittel schrumpft. Diese Grenze ist genau deshalb gesetzt und nicht höher; für wirklich große Zahlen braucht es andere Verfahren.

Probabilistische Primzahltests, die mit hoher Wahrscheinlichkeit statt mit Sicherheit antworten, und ihre Anwendung in der Kryptografie sind eigene Themen. Dieser Rechner antwortet beweisbar, weil er jeden Teiler wirklich ausprobiert; er teilt dafür keine Schlüssel ein und prüft keine Verschlüsselung.

Die Suche nach der nächsten Primzahl über einer Schranke führt der Rechner ebenfalls nicht aus: Er prüft eine eingegebene Zahl oder einen eingegebenen Bereich und sucht nicht selbst über dessen Ende hinaus weiter.

Bereiche mit mehr als 10.000 Zahlen werden abgewiesen, damit die Liste im Ergebnispanel lesbar bleibt und die Rechnung spürbar schnell. Ein großer Bereich lässt sich in Teilschritten von je 10.000 Zahlen abfragen.