Primzahlen-Check

Was ist eine Primzahl?

Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und durch sich selbst ohne Rest teilbar ist. Die ersten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23 und 29. Alle anderen Zahlen ab 2 heißen zusammengesetzte Zahlen: Sie lassen sich als Produkt kleinerer Zahlen schreiben, etwa 15 = 3 × 5. Der Rechner prüft, ob deine Zahl eine Primzahl ist, und zeigt bei zusammengesetzten Zahlen gleich die vollständige Primfaktorzerlegung an.

So wird gerechnet

Der Rechner arbeitet mit der sogenannten Probedivision:

• Zahlen kleiner als 2 (also 1, 0 und alle negativen Zahlen) sind keine Primzahlen.
• Ist die Zahl gerade, ist sie nur dann prim, wenn sie genau 2 ist.
• Sonst teilt der Rechner die Zahl nacheinander durch die ungeraden Zahlen 3, 5, 7, 9 … – aber nur so lange, wie der Teiler mal sich selbst nicht größer als die Zahl ist, also bis zur Quadratwurzel. Geht eine Division ohne Rest auf, ist die Zahl keine Primzahl. Findet sich bis dahin kein Teiler, ist sie prim.
• Für die Primfaktorzerlegung teilt der Rechner ab 2 so oft wie möglich durch jeden Teiler und notiert ihn jedes Mal. Was am Ende größer als 1 übrig bleibt, ist selbst eine Primzahl und der letzte Faktor.

Geprüft werden ganze Zahlen bis 9.007.199.254.740.991 (2⁵³ − 1). Bis zu dieser Grenze rechnet der Browser exakt; darüber hinaus würden Ziffern verloren gehen, deshalb lehnt der Rechner größere Zahlen ab. Auch Dezimalzahlen wie 7,5 werden nicht geprüft, weil es Primzahlen nur unter den ganzen Zahlen gibt.

Beispiel 1: Die Vorgabe 97

Voreingestellt ist 97. Die Zahl ist ungerade, also testet der Rechner die ungeraden Teiler. Die Wurzel aus 97 liegt bei etwa 9,85, deshalb genügen die Teiler 3, 5, 7 und 9; schon 11 × 11 = 121 ist größer als 97. Keiner dieser Teiler geht ohne Rest auf (97 ÷ 3 = 32 Rest 1, 97 ÷ 5 = 19 Rest 2, 97 ÷ 7 = 13 Rest 6, 97 ÷ 9 = 10 Rest 7). Ergebnis: 97 ist eine Primzahl – übrigens die größte unter 100. Die Nachbarzahl 96 dagegen ist gerade und zerfällt in 2 × 2 × 2 × 2 × 2 × 3.

Beispiel 2: 221 – sieht prim aus, ist es aber nicht

221 ist nicht durch 2, 3, 5, 7 oder 11 teilbar und wirkt deshalb auf den ersten Blick wie eine Primzahl. Die Wurzel aus 221 liegt bei etwa 14,87, der Test muss also bis 13 laufen. Erst dort geht die Division auf: 221 ÷ 13 = 17. Der Rechner meldet „221 ist keine Primzahl“ und zeigt die Primfaktoren 13 × 17. Solche Zahlen zeigen, warum ein Test mit ein paar kleinen Teilern nicht ausreicht.

Schritt für Schritt

1. Gib eine ganze Zahl in das Feld ein.
2. Das Ergebnis erscheint sofort: „ist eine Primzahl“ oder „ist keine Primzahl“.
3. Bei zusammengesetzten Zahlen steht darunter die Primfaktorzerlegung, aufsteigend sortiert.
4. Zur Kontrolle kannst du die Faktoren miteinander multiplizieren – das Produkt ist wieder deine Zahl.

Typische Werte

Mit dem Rechner geprüft:

Zahl	Ergebnis	Primfaktoren
1	keine Primzahl	– (per Definition ausgeschlossen)
2	Primzahl	einzige gerade Primzahl
9	keine Primzahl	3 × 3
51	keine Primzahl	3 × 17
57	keine Primzahl	3 × 19
91	keine Primzahl	7 × 13
97	Primzahl	–
100	keine Primzahl	2 × 2 × 5 × 5
561	keine Primzahl	3 × 11 × 17
1.001	keine Primzahl	7 × 11 × 13
2.027	Primzahl	–
7.919	Primzahl	–
1.000.003	Primzahl	–
2.147.483.647	Primzahl	231 − 1

51, 57 und 91 sind die klassischen „falschen Primzahlen“, die man im Kopf leicht für prim hält. Unter 100 gibt es genau 25 Primzahlen, unter 1.000 sind es 168.

Wann brauchst du den Primzahlen-Check?

In der Schule beim Kürzen von Brüchen und beim Bestimmen von größtem gemeinsamem Teiler und kleinstem gemeinsamem Vielfachen – beides geht über die Primfaktorzerlegung am einfachsten. Beim Programmieren, um die eigene Primzahlfunktion gegen ein Referenzergebnis zu prüfen. Beim Nachvollziehen von Verschlüsselungsverfahren wie RSA, die darauf beruhen, dass sich das Produkt zweier sehr großer Primzahlen kaum wieder zerlegen lässt. Oder einfach aus Neugier, ob dein Geburtsjahr oder deine Postleitzahl eine Primzahl ist.

Häufige Fehler und Grenzen

• 1 ist keine Primzahl: Primzahlen müssen größer als 1 sein. Sonst wäre die Primfaktorzerlegung nicht mehr eindeutig.
• Ungerade heißt nicht prim: 9, 15, 21, 51 oder 91 sind ungerade und trotzdem zusammengesetzt.
• Zu früh aufhören: Wer nur bis 7 oder 11 testet, hält 221 oder 1.001 für prim. Geprüft werden muss bis zur Quadratwurzel.
• Sehr große Zahlen: Über 2⁵³ − 1 rechnet der Rechner bewusst nicht, weil der Browser solche Zahlen nicht mehr exakt darstellt. Bei Primzahlen knapp unter dieser Grenze kann die Prüfung einen Augenblick dauern.
• Für Kryptografie ungeeignet: Zahlen für echte Verschlüsselung haben Hunderte Stellen und brauchen andere Testverfahren. Dieser Rechner ist für Schule, Lernen und Alltag gedacht.

Passende Rechner

Brüche kürzen und rechnen kannst du mit dem Bruchrechner, Anordnungen und Kombinationen zählt der Fakultät-Rechner. Zufällige Testzahlen liefert der Zufallszahlengenerator, und Gleichungen löst der Gleichungslöser.

Häufige Fragen

Ist 1 eine Primzahl?

Nein. Primzahlen sind per Definition größer als 1. Würde man die 1 mitzählen, ließe sich jede Zahl auf beliebig viele Arten als Produkt von Primzahlen schreiben, etwa 6 = 2 × 3 = 1 × 2 × 3.

Wie schnell ist die Prüfung bei großen Zahlen?

Der Rechner testet nur ungerade Teiler bis zur Quadratwurzel. Für Zahlen bis zu einigen Milliarden geht das praktisch sofort; bei 16-stelligen Primzahlen kurz unter der Obergrenze von 9.007.199.254.740.991 kann es einen Augenblick dauern.

Was zeigt der Rechner bei einer Nicht-Primzahl an?

Die Primfaktorzerlegung, also die Primzahlen, deren Produkt deine Zahl ergibt – aufsteigend sortiert und mehrfach vorkommende Faktoren wiederholt, zum Beispiel 100 = 2 × 2 × 5 × 5.

Warum reicht es, Teiler nur bis zur Quadratwurzel zu testen?

Teiler treten immer paarweise auf: Ist n = a × b und a größer als √n, muss b kleiner als √n sein. Findet sich bis zur Quadratwurzel kein Teiler, gibt es also auch darüber keinen.

Wofür werden Primzahlen in der Praxis verwendet?

Vor allem in der Kryptografie: Verfahren wie RSA nutzen aus, dass es sehr aufwendig ist, das Produkt zweier großer Primzahlen wieder in seine Faktoren zu zerlegen. Im Alltag begegnen sie dir beim Kürzen von Brüchen und bei Teilbarkeitsaufgaben.

Ist 2 die einzige gerade Primzahl?

Ja. Jede andere gerade Zahl ist durch 2 teilbar und hat damit neben 1 und sich selbst mindestens einen weiteren Teiler. Deshalb prüft der Rechner nach der 2 nur noch ungerade Teiler.

Können negative Zahlen oder Dezimalzahlen Primzahlen sein?

Nein. Primzahlen sind nach der üblichen Schuldefinition natürliche Zahlen größer als 1. Negative Zahlen und 0 meldet der Rechner als „keine Primzahl“, bei Dezimalzahlen bittet er um eine ganze Zahl.

Gibt es unendlich viele Primzahlen?

Ja, das hat schon Euklid bewiesen: Multipliziert man alle bekannten Primzahlen und addiert 1, ist das Ergebnis durch keine von ihnen teilbar – also muss es eine weitere Primzahl geben. Je größer die Zahlen werden, desto seltener werden Primzahlen allerdings.