Mathe & Statistik

Primzahl prüfen

Tragen Sie eine ganze Zahl bis eine Milliarde ein. Der Rechner zeigt, ob sie eine Primzahl ist, und gibt Teiler und Nachbar-Primzahlen an.

Ihre Zahl
Ganze Zahl von 2 bis 1.000.000.000.
Ergebnis

Aktualisiert am · Verantwortlich: Leon Blatz · 3 Quellen · So prüfen wir

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.

Eine Zahl n ist prim , wenn sie keinen Teiler zwischen 2und n besitzt\text{Eine Zahl n ist prim}\,{,}\ \quad \text{wenn}\ \text{sie keinen Teiler zwischen}\,2\quad \text{und}\ \sqrt{\text{n besitzt}}

Beispiel: Die Zahl 97 ist eine Primzahl. Sie hat nur die beiden Teiler 1 und 97. Die nächste größere Primzahl ist 101, die vorherige 89. Die Zahl 91 ist keine Primzahl, denn sie ist 7 mal 13, hat den kleinsten Teiler 7 und vier Teiler.

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.

PrimzahlJa, 2027 ist eine Primzahl
Zahl der Teiler2
Nächste größere Primzahl2029
Vorherige kleinere Primzahl2017

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.

PrimzahlNein, 561 ist keine Primzahl
Kleinster Teiler größer als 13
Zahl der Teiler8
Zerlegung3 · 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.

PrimzahlNein, 1001 ist keine Primzahl
Kleinster Teiler größer als 17
Vorherige kleinere Primzahl997
Nächste größere Primzahl1009

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).

PrimzahlNein, 3600 ist keine Primzahl
Zahl der Teiler45
Nächste größere Primzahl3607
Vorherige kleinere Primzahl3593

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.

PrimzahlJa, 2 ist eine Primzahl
Zahl der Teiler2
Vorherige kleinere Primzahlkeine
Nächste größere Primzahl3

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 Teiler100
Vorherige kleinere Primzahl999.999.937
Nächste größere Primzahl1.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

Diesen Rechner auf Ihrer Website einbinden

Kostenlos für Blogs, Vereine, Schulen und Unternehmen. Fügen Sie den Code in Ihre Seite ein, zum Beispiel als HTML-Block in WordPress.

Der Rechner läuft in einem Rahmen, setzt keine Cookies und speichert keine Eingaben. Bitte lassen Sie den Quellenlink unter dem Rahmen stehen. Höhe bei Bedarf anpassen.

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.