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