Primzahl-Rechner: Primzahlen prüfen und Teiler bestimmen

Bis 100 gibt es genau 25 Primzahlen: 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.

Der Rechner ermittelt diese Liste im Modus „Primzahlen auflisten“ mit dem Grenzwert 100 über das Sieb des Eratosthenes: Alle Zahlen von 2 bis 100 werden notiert, anschließend werden systematisch alle Vielfachen jeder bereits gefundenen Primzahl gestrichen.

Übrig bleiben ausschließlich Zahlen, die durch keine kleinere Zahl außer 1 teilbar sind. Die kleinste Primzahl in diesem Bereich ist 2, gleichzeitig die einzige gerade, die größte ist 97.

Wer nur eine einzelne Zahl aus diesem Bereich prüfen möchte, etwa ob 91 dazugehört, wechselt in den Modus „Eine Zahl prüfen“ – 91 ist übrigens keine Primzahl, sondern 7 × 13.

Für größere Bereiche wie 1.000 oder den Rechner-Grenzwert von 10.000 liefert derselbe Modus die vollständige, deutlich längere Liste in Sekunden.

Eine Primzahl ist per Definition eine natürliche Zahl größer als 1, die genau zwei positive Teiler besitzt: die 1 und sich selbst.

Die Zahl 1 hat aber nur einen einzigen Teiler, nämlich sich selbst, und erfüllt die Zweiteiler-Bedingung damit nicht – sie fällt komplett aus dem Primzahlbegriff heraus.

Der Rechner bestätigt das im Prüfmodus für die Eingabe 1 direkt mit der Meldung „Nein, 1 ist keine Primzahl“ und nennt als nächstgelegene Primzahl darüber die 2.

Der Ausschluss der 1 ist kein willkürliches Detail, sondern notwendig für den Fundamentalsatz der Arithmetik: Jede natürliche Zahl größer als 1 lässt sich eindeutig in Primfaktoren zerlegen.

Würde die 1 mitzählen, ließe sich jede Zerlegung beliebig oft um weitere Faktoren 1 ergänzen, etwa 6 = 2 × 3 oder ebenso 6 = 1 × 1 × 2 × 3, und die Eindeutigkeit wäre zerstört.

Aus demselben Grund beginnt auch das Sieb des Eratosthenes, das dieser Rechner im Listenmodus verwendet, erst bei der 2 und überspringt die 1 von vornherein.

Bis 1.000 zählt der Rechner genau 168 Primzahlen, die kleinste ist weiterhin 2, die größte in diesem Bereich ist 997.

Ermittelt wird die Liste im Modus „Primzahlen auflisten“ mit dem Grenzwert 1000 über dasselbe Sieb des Eratosthenes, das alle Vielfachen jeder gefundenen Primzahl systematisch ausschließt.

Zum Vergleich: Bis 100 sind es nur 25 Primzahlen, bis 10.000 bereits 1.229 – die Dichte der Primzahlen nimmt mit wachsendem Zahlenbereich spürbar ab, ohne jemals ganz zu verschwinden.

Für eine Hausaufgabe oder eine schnelle Übersicht reicht es, den Grenzwert im Rechner einzutragen; eine manuelle Prüfung aller 999 Kandidaten wäre dagegen sehr aufwendig.

Wer stattdessen nur wissen möchte, ob eine bestimmte dreistellige Zahl aus diesem Bereich prim ist, etwa 331 oder 517, wechselt in den Modus „Eine Zahl prüfen“: 331 ist tatsächlich eine Primzahl, während 517 = 11 × 47 keine ist – beide Ergebnisse liefert der Rechner inklusive Primfaktorzerlegung sofort.

Ja, 2 ist eine Primzahl – und zwar die einzige gerade Primzahl überhaupt. Der Rechner bestätigt das im Prüfmodus für die Eingabe 2 mit „Ja, 2 ist eine Primzahl“, weil zwischen 2 und der Wurzel aus 2 (rund 1) kein Teiler existiert.

Jede andere gerade Zahl außer der 2 ist automatisch keine Primzahl, denn sie ist durch 2 teilbar und besitzt damit mindestens drei Teiler: die 1, die 2 und sich selbst.

Dieser Sonderstatus der 2 wird häufig übersehen, weil viele Lernende Primzahl fälschlich mit ungerade gleichsetzen – dabei sind etwa 9, 15, 25 oder 33 ungerade und trotzdem keine Primzahlen, weil sie sich als 3 × 3, 3 × 5, 5 × 5 beziehungsweise 3 × 11 zerlegen lassen.

Als Faustregel gilt: Jede gerade Zahl größer als 2 lässt sich sofort als keine Primzahl ausschließen, ohne überhaupt eine Division auszuprobieren.

Genau dieser Schnelltest beschleunigt die Prüfung größerer Zahlen erheblich, weil er die Hälfte aller Kandidaten von vornherein aussortiert.

Ja, das reicht aus, und genau so arbeitet der Rechner im Hintergrund.

Wenn eine Zahl n einen Teiler d hätte, der größer als die Wurzel aus n ist, dann müsste der passende Gegenteiler n geteilt durch d automatisch kleiner als die Wurzel aus n sein – Teiler treten also immer paarweise auf, symmetrisch um die Quadratwurzel.

Findet der Test bis zur Wurzel keinen Teiler, kann darüber hinaus ebenfalls keiner mehr existieren.

Für die Zahl 97 bedeutet das: Die Wurzel aus 97 liegt bei etwa 9, also genügt es, die Teiler 2 bis 9 durchzuprobieren; keiner davon geht auf, also ist 97 prim.

Bei der Zahl 289 dagegen reicht der Test bis zur Wurzel 17, und genau dort wird er fündig: 289 = 17 × 17.

Diese Abkürzung beschleunigt den Primzahltest erheblich, weil bei einer sechsstelligen Zahl nur noch bis in den dreistelligen Bereich getestet werden muss statt bis zur vollen Zahl.

Der Rechner nutzt dieses Verfahren für jede Eingabe im Prüfmodus, unabhängig davon, wie groß die Zahl ist.

Eine einzige, breit etablierte Eselsbrücke wie beim Merken von Pi-Nachkommastellen gibt es für die 25 Primzahlen bis 100 nicht – dafür ist ihre Verteilung zu unregelmäßig, um sich in einen einprägsamen Reim zu pressen.

Bewährt hat sich stattdessen das systematische Vorgehen des Sieb des Eratosthenes: Zahlen von 2 bis 100 aufschreiben, dann nacheinander alle Vielfachen von 2, 3, 5 und 7 streichen – weitere Teiler müssen wegen der Quadratwurzel-Grenze (Wurzel aus 100 = 10) nicht geprüft werden.

Wer sich stattdessen Zehnerblöcke einprägen möchte, findet ein grobes Muster: Der erste Block von 1 bis 10 enthält mit 2, 3, 5 und 7 die meisten Primzahlen (4 Stück), der letzte Block von 91 bis 100 nur noch eine einzige, die 97.

Dazwischen liegen je Zehnerblock meist 2 oder 3 Primzahlen.

Der Rechner nimmt dir das Auswendiglernen ohnehin ab: Trage im Modus „Primzahlen auflisten“ den Grenzwert 100 ein, und die vollständige, garantiert korrekte Liste erscheint sofort, ganz ohne Eselsbrücke oder Merkvers.

Das kommt auf die einzelne Zahl an, denn zweistellige Zahlen sind keineswegs automatisch prim oder automatisch zusammengesetzt.

31 zum Beispiel ist eine Primzahl: Zwischen 2 und der Wurzel aus 31 (rund 5) gibt es keinen Teiler, die Nachbarn sind 29 darunter und 37 darüber.

51 dagegen ist keine Primzahl, sondern 3 × 17 – der Rechner findet 3 als kleinsten Teiler und liefert direkt die vollständige Zerlegung. Auch 69 ist zusammengesetzt: 69 = 3 × 23, ebenfalls mit 3 als kleinstem Teiler.

Eine schnelle Vorprüfung hilft: Ist die Quersumme durch 3 teilbar, ist es auch die Zahl selbst – bei 51 ist die Quersumme 5 + 1 = 6 und bei 69 ist sie 6 + 9 = 15, beide durch 3 teilbar, also keine Primzahlen.

Bei 31 ergibt die Quersumme dagegen 4, das ist nicht durch 3 teilbar, ein erster Hinweis, den der vollständige Test bis zur Quadratwurzel dann bestätigt.

Für jede beliebige zweistellige oder größere Zahl liefert der Prüfmodus des Rechners das exakte Ergebnis inklusive Primfaktorzerlegung in Sekunden.

Der Modus „Primzahlen auflisten“ akzeptiert Grenzwerte von 2 bis 10.000, weil das Sieb des Eratosthenes bei größeren Bereichen deutlich mehr Rechenzeit und Speicher benötigt und die Ergebnisliste sonst unhandlich lang würde.

Bis zum Grenzwert 10.000 liefert der Rechner alle 1.229 Primzahlen, die größte davon ist 9.973 – für Schulaufgaben, Übungen und die meisten praktischen Zwecke ist dieser Bereich mehr als ausreichend.

Wer einen größeren Wert einträgt, bekommt automatisch das Ergebnis für den Maximalwert 10.000 zurück, nicht für den eingetippten größeren Wert – ein wichtiger Hinweis, falls die Liste kürzer ausfällt als erwartet.

Für sehr große Bereiche bis zu einer Million oder mehr sind spezialisierte Primzahlentabellen oder Fachsoftware die passendere Wahl, weil dort mit optimierten Algorithmen und mehr Rechenleistung gearbeitet wird statt mit einem einfachen, dafür vollständig nachvollziehbaren Sieb.

Für den Prüfmodus einer einzelnen Zahl gilt dagegen eine andere, deutlich höhere Grenze von bis zu 10.000.000 – dort ist ausschließlich der Rechenaufwand pro Einzelzahl relevant, nicht die Länge einer Ergebnisliste.

Sobald die Primfaktorzerlegung zweier Zahlen vorliegt, lassen sich gemeinsame Teiler und Vielfache direkt ablesen, ohne weiter zu probieren.

Für den größten gemeinsamen Teiler (ggT) nimmst du von jedem gemeinsamen Primfaktor die kleinere vorkommende Potenz, für das kleinste gemeinsame Vielfache (kgV) die jeweils größere.

Beispiel: Der Rechner zerlegt 84 im Prüfmodus zu 84 = 2 × 2 × 3 × 7 und 90 zu 90 = 2 × 3 × 3 × 5. Gemeinsam sind die Faktoren 2 und 3, jeweils mit der kleineren Potenz genommen: 2¹ × 3¹ = 6 ist der ggT.

Für das kgV zählt jeder vorkommende Faktor mit der größeren Potenz: 2² × 3² × 5 × 7 = 1.260.

Dieselbe Zerlegung hilft auch beim Kürzen von Brüchen: Der Bruch 84/90 lässt sich direkt durch den ggT 6 teilen und wird zu 14/15, ohne weiter nach gemeinsamen Teilern zu suchen.

Wer regelmäßig mit Brüchen, ggT oder kgV arbeitet, sollte deshalb die Primfaktorzerlegung als Zwischenschritt nutzen, statt Teiler auf Verdacht auszuprobieren.