Primzahl-Prüfer
Geben Sie eine beliebige ganze Zahl bis zu einer Billion ein und erfahren Sie sofort, ob sie eine Primzahl oder eine zusammengesetzte Zahl ist. Der Rechner zeigt zusätzlich den kleinsten Primfaktor sowie die vollständige Primfaktorzerlegung mit Erklärung an.
Ist diese Zahl eine Primzahl?
Formel des Primzahl-Prüfers
Dabei ist:
- \(n\) — die zu prüfende ganze Zahl
- \(d\) — ein möglicher Teiler
- \(\sqrt{n}\) — die Quadratwurzel von \(n\), abgerundet auf die nächstkleinere ganze Zahl
Die Formel beschreibt das Verfahren der Probedivision: Es genügt, nach Teilern bis \(\sqrt{n}\) zu suchen, denn gilt \(n = a \times b\) mit beiden Faktoren größer als 1, kann mindestens einer davon nicht größer als \(\sqrt{n}\) sein. Aus diesem Grund testet der Rechner nur Kandidaten bis zur Quadratwurzel und überspringt dabei Vielfache von 2 und 3 (geprüft werden 2, 3 und anschließend alle Zahlen der Form \(6k \pm 1\)).
Primzahl-Prüfer – Rechenbeispiel
Beispiel: Ist 91 eine Primzahl? Wir prüfen mögliche Teiler bis \(\sqrt{91} \approx 9.54\), also müssen nur 2, 3, 5 und 7 getestet werden.
\[ 91 \div 2 = 45.5 \quad (\text{kein Teiler}) \]
\[ 91 \div 3 = 30.\overline{3} \quad (\text{kein Teiler}) \]
\[ 91 \div 5 = 18.2 \quad (\text{kein Teiler}) \]
\[ 91 \div 7 = 13 \quad (\text{exakt — 7 ist ein Teiler!}) \]
Ergebnis: 91 ist eine zusammengesetzte Zahl. Ihr kleinster Primfaktor ist 7, denn \(91 = 7 \times 13\), und die vollständige Primfaktorzerlegung lautet \(91 = 7 \times 13\).
So verwenden Sie den Primzahl-Prüfer
- Geben Sie die ganze Zahl, die Sie prüfen möchten, in das Feld Zu prüfende Zahl (n) ein. Zugelassen sind alle ganzen Zahlen von 0 bis 1.000.000.000.000 (1012).
- Lesen Sie das Urteil in der Zeile Ergebnis — Primzahl oder zusammengesetzt. Zahlen kleiner als 2 werden als weder prim noch zusammengesetzt ausgewiesen.
- Ist die Zahl zusammengesetzt, sehen Sie sich Ein Primfaktor (angezeigt, wenn zusammengesetzt) an — das ist die kleinste Primzahl, die Ihre Zahl teilt, zusammen mit ihrem Kofaktor.
- Lesen Sie den Abschnitt Vollständige Primfaktorzerlegung mit Erklärung, der die Zahl in Primfaktoren zerlegt und erläutert, wie das Ergebnis überprüft wurde.
Was ist eine Primzahl?
Eine Primzahl ist eine ganze Zahl größer als 1, die genau zwei positive Teiler hat: 1 und sich selbst. Die ersten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Jede andere ganze Zahl größer als 1 ist zusammengesetzt, das heißt, sie lässt sich als Produkt zweier kleinerer ganzer Zahlen schreiben, die beide größer als 1 sind.
Die Zahl 2 verdient eine besondere Erwähnung: Sie ist die einzige gerade Primzahl, denn jede andere gerade Zahl ist durch 2 teilbar. Die Zahlen 0 und 1 sind weder prim noch zusammengesetzt — 1 hat nur einen einzigen Teiler, und 0 ist durch jede positive ganze Zahl teilbar, sodass keine von beiden die Definition „genau zwei Teiler“ erfüllt.
Primzahlen sind die Bausteine der Arithmetik. Der Hauptsatz der elementaren Zahlentheorie (Fundamentalsatz der Arithmetik) besagt, dass sich jede ganze Zahl größer als 1 auf genau eine Weise in Primfaktoren zerlegen lässt (abgesehen von der Reihenfolge der Faktoren). Deshalb zeigt der Rechner bei zusammengesetzten Zahlen stets die vollständige Primfaktorzerlegung an: Sie verrät Ihnen genau, aus welchen Primzahl-Bausteinen Ihre Zahl besteht und wie oft jeder davon vorkommt.
Das Ergebnis zu deuten ist unkompliziert. Lautet das Urteil prim, lässt sich die Zahl nicht weiter zerlegen. Lautet es zusammengesetzt, ist der angezeigte kleinste Primfaktor der einfachste Beweis — teilt man die Zahl durch diesen Faktor, ergibt sich eine ganze Zahl, womit die Primalität sofort ausgeschlossen ist.
Voraussetzungen, Grenzen und Tipps
- Zahlenbereich: Der Rechner akzeptiert ganze Zahlen von 0 bis 1012. Für größere Zahlen sind aufwändigere Methoden nötig.
- Verfahren: Verwendet wird die Probedivision mit der Optimierung \(6k \pm 1\) — schnell und mathematisch sicher im unterstützten Zahlenbereich. Für astronomisch große Zahlen greift man stattdessen auf probabilistische Tests wie den kleinen Satz von Fermat zurück, weil die Probedivision trotz ihrer Exaktheit zu langsam wird.
- Dezimalzahlen und negative Zahlen: Primalität ist nur für ganze Zahlen größer als 1 definiert. Bei Dezimaleingaben, negativen Zahlen sowie 0 oder 1 erhalten Sie daher eine Erklärung statt eines Urteils.
- Schnelle Kopfrechnungen: Oft lässt sich die Primalität schon vor der Nutzung des Rechners im Kopf ausschließen — eine Zahl, die auf 0, 2, 4, 5, 6 oder 8 endet, ist durch 2 oder 5 teilbar, und eine Zahl, deren Quersumme ein Vielfaches von 3 ist (wie bei 91, denn 9 + 1 = 10 … Probe: 10 ist nicht durch 3 teilbar, dieser Trick greift hier also nicht), ist durch 3 teilbar. Der Quersummentest hängt mit der Quersumme bzw. iterierten Quersumme zusammen.
- Warum die Zerlegung wichtig ist: Primfaktorzerlegungen sind die Grundlage vieler zahlentheoretischer Werkzeuge — von der in der Kryptographie verwendeten multiplikativen Inversen modulo n bis zur Lösung von Kongruenzsystemen mit dem Chinesischen Restsatz.
Häufig gestellte Fragen
Wie kann ich von Hand prüfen, ob eine Zahl eine Primzahl ist?
Testen Sie, ob irgendeine ganze Zahl von 2 bis \(\sqrt{n}\) Ihre Zahl ohne Rest teilt. Wenn keine das tut, ist die Zahl eine Primzahl. Für 137 gilt \(\sqrt{137} \approx 11.7\), Sie prüfen also nur 2, 3, 5, 7 und 11 — keine davon teilt 137, also ist 137 prim. Lassen Sie nach der Prüfung von 2 alle geraden Kandidaten weg, um Zeit zu sparen, und denken Sie daran: Über die Quadratwurzel hinaus müssen Sie nie testen.
Warum ist 1 keine Primzahl?
Eine Primzahl muss genau zwei positive Teiler haben: 1 und sich selbst. Die Zahl 1 hat nur einen Teiler und erfüllt die Definition daher nicht. Diese Konvention hält außerdem den Fundamentalsatz der Arithmetik aufrecht — wäre 1 eine Primzahl, hätte jede Zahl größer als 1 unendlich viele Zerlegungen wie \(6 = 2 \times 3 = 2 \times 3 \times 1\). Deshalb ist 1 weder prim noch zusammengesetzt.
Welche Teilbarkeitsregeln helfen am schnellsten vor dem Test?
Prüfen Sie die letzte Ziffer: Zahlen, die auf 0, 2, 4, 5, 6 oder 8 enden, sind durch 2 oder 5 teilbar. Addieren Sie die Ziffern — ist die Summe durch 3 teilbar, ist es auch die Zahl (für 87: \(8 + 7 = 15\), teilbar durch 3, also ist 87 zusammengesetzt). Für die 11 addieren und subtrahieren Sie die Ziffern abwechselnd; ist das Ergebnis durch 11 teilbar, ist es die Zahl auch. Diese Regeln schließen die meisten zusammengesetzten Zahlen sofort aus.
Was ist der Unterschied zwischen Primzahlen und teilerfremden Zahlen?
Primalität ist eine Eigenschaft einer einzelnen Zahl: Sie hat genau zwei Teiler. Teilerfremdheit ist eine Eigenschaft eines Paares: Zwei Zahlen sind teilerfremd, wenn ihr größter gemeinsamer Teiler 1 ist. So sind 8 und 15 beide zusammengesetzt, aber dennoch teilerfremd, denn \(\ggT(8, 15) = 1\). Beachten Sie: 2 und 3 sind teilerfremd, aber auch 4 und 9 — keine der beiden Zahlen muss selbst prim sein.
Welche Zahlen wirken wie Primzahlen, sind es aber nicht?
Bekannte „Scheinprimzahlen“ sind 91 (\(= 7 \times 13\)), 57 (\(= 3 \times 19\)), 51 (\(= 3 \times 17\)), 87 (\(= 3 \times 29\)) und 119 (\(= 7 \times 17\)). Sie werden übersehen, weil sie weder durch 2 oder 5 noch durch ein offensichtliches Quadrat teilbar sind. Wer von Hand prüft, sollte daher 3 (Quersumme), 7 und 11 besonders sorgfältig testen — diese drei fassen die meisten heiklen Fälle unter 150.
Wie finde ich Schritt für Schritt die Primfaktorzerlegung einer Zahl?
Teilen Sie wiederholt durch die kleinste Primzahl, die passt. Für 360: durch 2 ergibt 180, durch 2 ergibt 90, durch 2 ergibt 45; 45 ist ungerade, also durch 3 ergibt 15, und durch 3 ergibt 5. Daraus folgt \(360 = 2^3 \times 3^2 \times 5\). Fahren Sie fort, bis der Rest selbst eine Primzahl ist. Dass jeder Divisionsschritt mit irgendeiner Primzahl gelingt, ist durch den Fundamentalsatz der Arithmetik garantiert.
Gibt es unendlich viele Primzahlen?
Ja — Euklid hat das um 300 v. Chr. bewiesen. Angenommen, es gäbe eine größte Primzahl: Multipliziert man alle bekannten Primzahlen und addiert 1, ist das Ergebnis durch keine von ihnen teilbar und muss folglich einen neuen Primfaktor besitzen. Unter einer Million liegen 78.498 Primzahlen, unter einer Billion etwa \(\pi(10^{12}) \approx 37.6\) Milliarden. Die Lücken zwischen Primzahlen wachsen im Durchschnitt, aber neue Rekordprimzahlen werden laufend entdeckt — die jüngsten Funde sind über 24 Millionen Ziffern lang.