Was eine Primzahl auszeichnet
Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und durch sich selbst teilbar ist. Die ersten Primzahlen sind 2, 3, 5, 7, 11, 13, 17 und 19. Die 2 ist die einzige gerade Primzahl. Alle anderen natürlichen Zahlen größer als 1 sind zusammengesetzt und lassen sich als Produkt von Primzahlen schreiben, den Primfaktoren.
Zum Prüfen nutzt der Rechner die Probedivision: Er teilt die Zahl durch alle Kandidaten bis zu ihrer Wurzel. Findet sich kein Teiler, ist die Zahl prim. Das reicht, weil ein Teiler über der Wurzel immer einen Partner darunter hat. Zusätzlich nennt der Rechner den kleinsten Teiler, die Zahl aller Teiler und die nächste größere und vorherige kleinere Primzahl.
Primzahlen sind seit der Antike ein zentrales Thema der Mathematik, und heute sind sie in der Kryptografie unverzichtbar: Verschlüsselungsverfahren wie RSA beruhen darauf, dass es leicht ist, große Primzahlen zu multiplizieren, aber schwer, das Produkt wieder zu zerlegen.
Interessantes zu Primzahlen
Es gibt unendlich viele Primzahlen, wie schon Euklid vor über 2.000 Jahren bewies. Ihre Verteilung ist unregelmäßig: Es gibt Primzahlzwillinge wie 11 und 13, die nur zwei auseinanderliegen, und beliebig große Lücken ohne Primzahl. Die größte bekannte Primzahl hat über 40 Millionen Stellen und wurde mit Computern gefunden, meist als Mersenne-Primzahl.
Der Hauptsatz der Arithmetik besagt, dass jede natürliche Zahl größer als 1 auf genau eine Weise als Produkt von Primzahlen darstellbar ist. Die Zerlegung berechnet der Primfaktorzerlegung-Rechner. Auf ihr beruhen das kleinste gemeinsame Vielfache und der größte gemeinsame Teiler.
Der Rechner ist für Zahlen bis eine Milliarde ausgelegt. Für größere Zahlen nutzt man schnellere Testverfahren wie Miller-Rabin. Die Berechnung ist exakt, solange die Zahl in ganzen Zahlen dargestellt wird.
Im Alltag begegnen Primzahlen bei Zahlenrätseln, in Schule und Studium sowie bei Hashfunktionen und Zufallszahlen in der Informatik.
Rechenbeispiele Schritt für Schritt
Ist 2027 eine Primzahl?
Eine beliebte Frage zum Jahreswechsel. Geprüft werden muss nur bis zur Wurzel von 2027, also bis 45.
| Primzahl | Ja, 2027 ist eine Primzahl |
|---|---|
| Zahl der Teiler | 2 |
| Nächste größere Primzahl | 2029 |
| Vorherige kleinere Primzahl | 2017 |
2027 ist eine Primzahl. Zusammen mit 2029 bildet sie sogar ein Primzahlzwillingspaar.
Die Zahl 561: sieht unauffällig aus, ist aber besonders
561 ist durch 3 teilbar, die Quersumme 12 verrät es. Sie ist zugleich die kleinste Carmichael-Zahl, die einfache Primzahltests nach dem kleinen Satz von Fermat täuscht.
| Primzahl | Nein, 561 ist keine Primzahl |
|---|---|
| Kleinster Teiler größer als 1 | 3 |
| Zahl der Teiler | 8 |
| Zerlegung | 3 · 11 · 17 |
561 = 3 · 11 · 17 ist keine Primzahl. Die Probedivision des Rechners erkennt das sicher, ein reiner Fermat-Test nicht.
1001 = 7 · 11 · 13 und eine Primzahllücke
1001 hat keinen der Teiler 2, 3 oder 5, wirkt deshalb auf den ersten Blick prim. Der kleinste Teiler ist 7.
| Primzahl | Nein, 1001 ist keine Primzahl |
|---|---|
| Kleinster Teiler größer als 1 | 7 |
| Vorherige kleinere Primzahl | 997 |
| Nächste größere Primzahl | 1009 |
Zwischen 997 und 1009 liegt keine einzige Primzahl, eine Lücke von 12. Solche Lücken werden mit wachsender Zahl im Mittel größer.
3600: viele Teiler
3600 = 2⁴ · 3² · 5². Die Teilerzahl ergibt sich aus den Exponenten: (4 + 1) · (2 + 1) · (2 + 1).
| Primzahl | Nein, 3600 ist keine Primzahl |
|---|---|
| Zahl der Teiler | 45 |
| Nächste größere Primzahl | 3607 |
| Vorherige kleinere Primzahl | 3593 |
3600 hat 45 Teiler. Deshalb eignet sich die Zahl gut zum Aufteilen, etwa Sekunden einer Stunde in gleich große Abschnitte.
Grenzfall: die Zahl 2
Die kleinste Primzahl und die einzige gerade. Eine kleinere Primzahl gibt es nicht.
| Primzahl | Ja, 2 ist eine Primzahl |
|---|---|
| Zahl der Teiler | 2 |
| Vorherige kleinere Primzahl | keine |
| Nächste größere Primzahl | 3 |
2 ist prim, 2 und 3 sind die einzigen aufeinanderfolgenden natürlichen Zahlen, die beide Primzahlen sind.
Obergrenze: eine Milliarde
Die größte Zahl, die der Rechner prüft. Als Zehnerpotenz ist sie offensichtlich nicht prim, spannend sind die Nachbarn.
| Zahl der Teiler | 100 |
|---|---|
| Vorherige kleinere Primzahl | 999.999.937 |
| Nächste größere Primzahl | 1.000.000.007 |
Die nächste Primzahl nach einer Milliarde ist 1.000.000.007. Sie wird in der Informatik gern als Modulus für Rechnungen mit großen Zahlen verwendet.
Sonderfälle und Grenzen
- Pseudoprimzahlen: Schnelle Tests nach dem kleinen Satz von Fermat halten einige zusammengesetzte Zahlen für prim, etwa die Carmichael-Zahlen 561, 1105 und 1729. Die Probedivision dieses Rechners ist dagegen exakt.
- Kryptografie: Für Verschlüsselung werden Primzahlen mit Hunderten von Dezimalstellen verwendet. Diese prüft man mit probabilistischen Tests wie Miller-Rabin, eine Probedivision wäre dafür viel zu langsam.
- Teilerzahl aus der Zerlegung: Ist n = p₁^a · p₂^b · …, dann hat n genau (a + 1) · (b + 1) · … Teiler. So lässt sich das Ergebnis des Rechners mit dem Primfaktorzerlegung-Rechner nachprüfen.
- Rekordprimzahlen: Die größte bekannte Primzahl wird nicht mit Probedivision, sondern mit speziellen Tests für Mersenne-Zahlen der Form 2^p − 1 gefunden. Rekordangaben veralten, sobald eine größere entdeckt wird.
- Nur ganze Zahlen: Dezimalzahlen, Brüche und Zahlen über einer Milliarde werden nicht geprüft. Die nächste größere Primzahl kann aber über einer Milliarde liegen, wie bei 1.000.000.007.
Mehr zum Thema Primzahlen und Teiler
Häufige Fragen
Welche Primzahlen gibt es bis 100?
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. Um sie zu finden, genügt es, die Vielfachen von 2, 3, 5 und 7 zu streichen, denn die Wurzel aus 100 ist 10.
Wie viele Primzahlen gibt es unter einer Million?
Unter einer Million gibt es 78.498 Primzahlen, unter einer Milliarde 50.847.534. Primzahlen werden also seltener, je größer die Zahlen sind. Nach dem Primzahlsatz liegt in der Nähe einer Zahl n etwa jede ln(n)-te Zahl prim, bei einer Milliarde also ungefähr jede 21. Zahl.
Was ist das Sieb des Eratosthenes?
Ein Verfahren, um alle Primzahlen bis zu einer Grenze zu finden. Sie schreiben alle Zahlen ab 2 auf, nehmen die kleinste noch nicht gestrichene Zahl als Primzahl und streichen alle ihre Vielfachen. Das wiederholen Sie, bis die Wurzel der Grenze erreicht ist. Alle übrigen Zahlen sind Primzahlen.
Was sind Primzahlzwillinge?
Zwei Primzahlen, die sich nur um 2 unterscheiden, etwa 11 und 13, 17 und 19 oder 2027 und 2029. Ob es unendlich viele Primzahlzwillinge gibt, ist bis heute nicht bewiesen. Bekannt ist aber, dass es unendlich viele Primzahlpaare mit einem Abstand von höchstens 246 gibt.
Sind 0, 1 oder negative Zahlen Primzahlen?
Nein. Primzahlen sind nach der üblichen Definition natürliche Zahlen größer als 1. Die 1 ist ausgenommen, damit die Zerlegung in Primfaktoren eindeutig bleibt. Die 0 ist durch jede Zahl teilbar. In der Algebra gilt −7 zwar als Primelement, als Primzahlen zählen aber nur positive Zahlen. Der Rechner akzeptiert deshalb nur Zahlen ab 2.
Woran erkenne ich schnell, dass eine Zahl keine Primzahl ist?
Endet sie auf 0, 2, 4, 5, 6 oder 8, ist sie durch 2 oder 5 teilbar, ausgenommen 2 und 5 selbst. Ist die Quersumme durch 3 teilbar, ist es auch die Zahl. Für 11 hilft die alternierende Quersumme: Bei 1001 ergibt 1 − 0 + 0 − 1 null, also ist 1001 durch 11 teilbar.
Quellen und Rechtsgrundlagen
- NIST Digital Library of Mathematical Functions, § 27.2 Functions (Primzahlen) National Institute of Standards and Technology
- NIST Digital Library of Mathematical Functions, Kapitel 27 Functions of Number Theory National Institute of Standards and Technology
- ISO 80000-2: Quantities and units, Mathematics International Organization for Standardization
Alle Berechnungen erfolgen direkt in Ihrem Browser, Ihre Eingaben werden nicht übertragen oder gespeichert. Die Ergebnisse sind Orientierungswerte ohne Gewähr und ersetzen keine steuerliche, rechtliche oder finanzielle Beratung. Die Erklärtexte auf dieser Seite wurden mit KI erstellt. Letzte inhaltliche Änderung dieser Seite: . Mehr dazu: So entstehen und prüfen wir die Rechner.