Primzahl-Prüfer — bis zu 1.000 Stellen, kostenlos
Prüfen Sie sofort, ob eine Zahl mit bis zu 1.000 Stellen prim ist. Mit Primfaktorzerlegung, Nachbarprimzahlen, Probedivision und dem verwendeten Testverfahren.
Alle 168 Primzahlen unter 1.000
| 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 |
| 41 | 43 | 47 | 53 | 59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 |
| 97 | 101 | 103 | 107 | 109 | 113 | 127 | 131 | 137 | 139 | 149 | 151 |
| 157 | 163 | 167 | 173 | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 |
| 227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 | 281 |
| 283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 | 349 | 353 | 359 |
| 367 | 373 | 379 | 383 | 389 | 397 | 401 | 409 | 419 | 421 | 431 | 433 |
| 439 | 443 | 449 | 457 | 461 | 463 | 467 | 479 | 487 | 491 | 499 | 503 |
| 509 | 521 | 523 | 541 | 547 | 557 | 563 | 569 | 571 | 577 | 587 | 593 |
| 599 | 601 | 607 | 613 | 617 | 619 | 631 | 641 | 643 | 647 | 653 | 659 |
| 661 | 673 | 677 | 683 | 691 | 701 | 709 | 719 | 727 | 733 | 739 | 743 |
| 751 | 757 | 761 | 769 | 773 | 787 | 797 | 809 | 811 | 821 | 823 | 827 |
| 829 | 839 | 853 | 857 | 859 | 863 | 877 | 881 | 883 | 887 | 907 | 911 |
| 919 | 929 | 937 | 941 | 947 | 953 | 967 | 971 | 977 | 983 | 991 | 997 |
Jede andere Zahl unter 1.000 ist zusammengesetzt: Sie hat mindestens einen Teiler außer 1 und sich selbst.
Wie viele Primzahlen liegen unter den einzelnen Zehnerpotenzen?
| Bis | Primzahlen, π(x) | Anteil der Primzahlen |
|---|---|---|
| 10 | 4 | 40% |
| 100 | 25 | 25% |
| 1,000 | 168 | 16.8% |
| 10⁴ | 1,229 | 12.29% |
| 10⁵ | 9,592 | 9.59% |
| 10⁶ | 78,498 | 7.85% |
| 10⁷ | 664,579 | 6.65% |
| 10⁸ | 5,761,455 | 5.76% |
| 10⁹ | 50,847,534 | 5.08% |
| 10¹⁰ | 455,052,511 | 4.55% |
| 10¹² | 37,607,912,018 | 3.76% |
| 10¹⁵ | 29,844,570,422,669 | 2.98% |
π(x) ist die Primzahlzählfunktion: wie viele Primzahlen x nicht überschreiten. Der Anteil nimmt immer weiter ab — in der Nähe von x ist etwa eine von ln(x) Zahlen prim — er erreicht aber niemals Null, denn es gibt unendlich viele Primzahlen.
Was ist ein Primzahl-Prüfer?
Ein Primzahl-Prüfer stellt fest, ob eine eingegebene ganze Zahl außer 1 und sich selbst keine weiteren Teiler besitzt. Bei kleinen Zahlen lässt sich das von Hand per Probedivision nachvollziehen. Bei großen Zahlen jedoch – etwa Kandidaten für kryptografische Schlüssel, Aufgaben aus Mathematikwettbewerben oder Zahlen mit mehreren hundert Stellen – wird die Probedivision in vertretbarer Zeit unmöglich, sodass ein probabilistisches oder hybrides deterministisches Verfahren nötig ist.
Dieses Werkzeug akzeptiert ganze Zahlen mit bis zu 1.000 Stellen und wählt automatisch das schnellste Verfahren, das dennoch ein mathematisch verlässliches Ergebnis liefert: Probedivision für kleine Zahlen, einen deterministischen Miller-Rabin-Test für Zahlen unter rund 3,3 × 10²⁴ und Baillie-PSW für alles Größere. Zusätzlich zeigt es die Primfaktorzerlegung, die benachbarten Primzahlen und das jeweils verwendete Testverfahren an.
So prüfen Sie, ob eine Zahl eine Primzahl ist
- Zahl eingeben Geben Sie eine ganze Zahl mit bis zu 1.000 Stellen in das Eingabefeld ein oder fügen Sie sie ein. Kommas und Leerzeichen werden automatisch ignoriert.
- Ergebnis ablesen Das Ergebnis zeigt, ob die Zahl prim, zusammengesetzt oder der Sonderfall 1 ist, sowie das dabei verwendete Testverfahren.
- Details prüfen Sehen Sie sich die Primfaktorzerlegung, die Nachbarprimzahlen und zahlentheoretische Eigenschaften wie Primzahlzwillinge oder Mersenne-Primzahlen an.
- Probedivision nachvollziehen Bei kleineren Zahlen können Sie in der Tabelle genau sehen, mit welchen Teilern tatsächlich geprüft wurde.
Tipps für die Nutzung
- Eine Primzahl ist eine ganze Zahl größer als 1, deren einzige Teiler 1 und sie selbst sind. Die Folge beginnt mit 2, 3, 5, 7, 11, 13, … und endet nie.
- Der einfachste Primzahltest ist die Probedivision: Dividieren Sie N durch jede ganze Zahl von 2 bis √N. Bei √N aufzuhören genügt, denn wenn N = a × b gilt, kann der kleinere der beiden Faktoren √N nicht überschreiten.
- Von Hand lassen sich die meisten Zahlen in Sekunden ausschließen: gerade Zahlen (außer der 2), Zahlen mit einer 5 am Ende und Zahlen, deren Ziffernsumme ein Vielfaches von 3 ist, sind alle zusammengesetzt. Außerdem hat jede Primzahl größer als 3 die Form 6k − 1 oder 6k + 1.
- Bei großen Zahlen ist die Probedivision aussichtslos, deshalb verwenden Computer den Miller-Rabin- und den Baillie–PSW-Test. Diese Seite führt beide aus, sodass Sie eine Zahl mit bis zu 1.000 Stellen einfügen und dennoch in weniger als einer Sekunde eine Antwort erhalten.
- 1 ist keine Primzahl — die Definition verlangt "größer als 1" — und 2 ist die einzige gerade Primzahl, weil jede größere gerade Zahl durch 2 teilbar ist.
Anwendungsfälle
Hausaufgaben oder Wettbewerbsaufgaben überprüfen
Bestätigen Sie schnell, ob eine in einem Beweis oder einer Übungsaufgabe genannte Primzahl tatsächlich stimmt – bei einer falschen Angabe wird gleich die Zerlegung mitgeliefert.
Kryptografie-Konzepte erkunden
Testen Sie große Kandidatenzahlen und vergleichen Sie, wie Probedivision im Gegensatz zu Miller-Rabin und Baillie-PSW bei derselben Eingabe funktioniert – ähnlich wie bei RSA-Schlüsseln.
Besondere Eigenschaften einer Zahl prüfen
Finden Sie ohne Nachschlagewerk heraus, ob eine Zahl ein Primzahlzwilling, eine Sophie-Germain-, Mersenne- oder Fermat-Primzahl ist.
Programmieren und Algorithmen lernen
Nutzen Sie die Schritt-für-Schritt-Tabelle der Probedivision, um genau nachzuvollziehen, wie ein Primzahltest zu seinem Ergebnis kommt, bevor Sie ihn selbst implementieren.
Glossar
- Primzahl
- Eine ganze Zahl größer als 1, die außer 1 und sich selbst keine weiteren Teiler hat. Die Folge beginnt mit 2, 3, 5, 7, 11, 13, … und endet nie.
- Zusammengesetzte Zahl
- Eine ganze Zahl, die neben 1 und sich selbst noch weitere Teiler besitzt und sich als Produkt von Primzahlen darstellen lässt.
- Probedivision
- Prüft, ob eine ganze Zahl von 2 bis √N die Zahl N teilt. Ein vollständiger Beweis, der bei sehr großen Zahlen jedoch zu langsam wird.
- Miller-Rabin-Test
- Ein Test, der auf den Eigenschaften der Quadratwurzeln von 1 modulo N beruht. Mit ausreichend vielen Testbasen ist er für Zahlen unter etwa 3,3 × 10²⁴ deterministisch.
- Baillie-PSW-Test
- Eine Kombination aus Miller-Rabin-Test und starkem Lucas-Test für Zahlen, die für einen deterministischen Test zu groß sind. Bislang ist keine zusammengesetzte Zahl bekannt, die ihn besteht.
- Wahrscheinliche Primzahl
- Eine Zahl, die einen starken Primzahltest wie Baillie-PSW bestanden hat, ohne einen vollständigen deterministischen Beweis – äußerst wahrscheinlich prim, aber mathematisch nicht sicher.
- Primzahlzwilling
- Eine Primzahl, die sich von einer anderen Primzahl um genau 2 unterscheidet, etwa 11 und 13. Ob es unendlich viele davon gibt, ist ein ungelöstes mathematisches Problem.
- Mersenne-Primzahl
- Eine Primzahl der Form 2^p − 1. Die größten je entdeckten Primzahlen sind fast immer Mersenne-Primzahlen, gefunden durch verteilte Rechenprojekte wie GIMPS.
Häufige Fragen
Übrigens – Warum Primzahlen so wichtig sind
Primzahlen werden oft die "Atome der Arithmetik" genannt. Der Fundamentalsatz der Arithmetik besagt, dass jede ganze Zahl größer als 1 auf genau eine Weise als Produkt von Primzahlen geschrieben werden kann. Primzahlen sind damit die unteilbaren Bausteine, aus denen sich alle ganzen Zahlen zusammensetzen. Genau deshalb ist auch die oben angezeigte Zerlegung eindeutig: 360 ist 2³ × 3² × 5 und nichts anderes.
Eine riesige Zahl zu prüfen ist eine andere Aufgabe, als sie zu zerlegen, und die Geschichte dieses Unterschieds ist lesenswert. Der kleine Satz von Fermat liefert einen schnellen Test, doch manche zusammengesetzten Zahlen bestehen ihn zu jeder Basis — die kleinste davon ist 561, die Sie über die Schaltfläche oben ausprobieren können (man nennt sie Carmichael-Zahlen). Der Miller-Rabin-Test schließt diese Lücke, indem er unterwegs die Quadratwurzeln von 1 betrachtet, und wird mit den ersten 13 Primzahlen als Basen zu einem nachweislich deterministischen Test für alle Zahlen unter etwa 3,3 × 10²⁴. Darüber hinaus ergänzt diese Seite einen starken Lucas-Test zum Baillie–PSW-Verfahren: Bis heute wurde keine zusammengesetzte Zahl gefunden, die ihn besteht, ein Beweis fehlt jedoch — deshalb werden sehr große Ergebnisse als "wahrscheinlich prim" gekennzeichnet.
Diese Asymmetrie — leicht zu prüfen, schwer zu zerlegen — macht die moderne Kryptografie überhaupt möglich. Die RSA-Verschlüsselung, die weiterhin HTTPS-Verkehr und digitale Signaturen schützt, multipliziert zwei große Primzahlen zu einem öffentlichen Schlüssel. Diese Primzahlen aus dem Produkt zurückzugewinnen gilt als praktisch unmöglich, sodass sich dieselben Zahlen mühelos verifizieren, aber nicht zerlegen lassen. Den Unterschied können Sie auf dieser Seite selbst beobachten: Eine Zahl mit 1.000 Stellen wird fast augenblicklich als prim oder zusammengesetzt eingeordnet, während ein 60-stelliges Produkt aus zwei 30-stelligen Primzahlen die Zerlegung scheitern lässt.
Primzahlen bergen zudem einige der ältesten offenen Fragen der Mathematik. Niemand weiß, ob es unendlich viele Primzahlzwillinge gibt — Paare wie 11 und 13 oder 1.000.000.000.061 und 1.000.000.000.063 — obwohl Euklid bereits um 300 v. Chr. bewies, dass die Primzahlen selbst nie ausgehen. Auch die Jagd auf Rekordprimzahlen geht weiter: Freiwillige des GIMPS-Projekts durchsuchen Mersenne-Zahlen der Form 2^p − 1, und die größte bislang bekannte Primzahl, 2024 gefunden, ist 2¹³⁶²⁷⁹⁸⁴¹ − 1 mit 41.024.320 Stellen.