Prüfer für Primzahlen
Prüfen Sie, ob eine Zahl prim ist und finden Sie ihre Faktoren. Verwenden Sie diesen kostenlosen Primzahlprüfer, um jede Zahl sofort zu testen und alle Primfaktoren zu finden. Keine Anmeldung erforderlich.
Was ist eine Primzahl?
Eine Primzahl ist eine natürliche Zahl größer als 1, die genau zwei verschiedene Faktoren hat: 1 und sich selbst. Die ersten Primzahlen sind: 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...
Wichtige Fakten über Primzahlen:
- 2 ist die einzige gerade Primzahl.Jede andere gerade Zahl ist durch 2 teilbar, also hat sie mehr als zwei Faktoren.
- 1 ist nicht prim.Die Ausnahme von 1 bewahrt die Einzigartigkeit der Primfaktorisierung (Fundamentaltheorem der Arithmetik).
- Primzahlen sind unendlich.Euklid bewies dies um 300 v. Chr.: Nehmen wir eine endliche Liste aller Primzahlen p1, p2, ..., pn. Dann ist die Zahl (p1 x p2 x ... x pn) + 1 entweder selbst prim oder hat einen Primfaktor, der nicht in der Liste ist - Widerspruch. Daher ist die Liste unendlich.
- Wenn die Zahlen größer werden, werden die Primzahlen seltener -- aber sieNiemals aufhören. Es gibt 25 Primzahlen unter 100, 168 unter 1.000 und 78.498 unter 1.000.000.
A zusammengesetzte ZahlDie Zahl 12 ist zusammengesetzt, weil 12 = 2 x 6 = 3 x 4 = 2 x 2 x 3. Jede zusammengesetzte Zahl hat eine einzigartige Primfaktorisierung (Fundamental Theorem der Arithmetik).
Wie man überprüft, ob eine Zahl Prim ist
Es gibt mehrere Methoden zum Testen der Primalität, von der einfachen Versuchsabteilung bis hin zu fortgeschrittenen probabilistischen Algorithmen:
Versuchsabteilung (Grundmethode):Testen Sie, ob eine ganze Zahl von 2 bis √n n gleichmäßig teilt. Wenn dies nicht der Fall ist, ist n prim. Sie müssen nur bis √n überprüfen, denn wenn n = a x b mit a <= b, dann a <= √n. Wenn bis √n kein Teiler gefunden wird, gibt es auch keinen über √n.
Optimierte Versuchsabteilung:Nach Prüfung der Teilbarkeit durch 2 werden nur ungerade Zahlen geprüft. Weiterhin werden 2, 3 geprüft, dann nur Zahlen der Form 6k+/-1 (da alle Primzahlen > 3 dieser Form angehören). Dies reduziert die Anzahl der Tests um etwa 66% im Vergleich zur naiven Versuchsteilung.
| Zahl | √n (etwa) | Prüfteiler bis zu | Prime? Was ist das? |
|---|---|---|---|
| 97 | 9,85 | 2, 3, 5, 7 | Ja (nicht gleichmäßig verteilt) |
| 91 | 9,54 | 2, 3, 5, 7 | Nr. (7 x 13 = 91) |
| 1.009 | 31.76 | Bis zu 31 | Ja (primär) |
| 1 001 | 31.64 | Bis zu 31 | Nr. (7 x 11 x 13 = 1.001) |
| 7.919 | 88 und 99 | Bis zu 89 | Ja (die tausendste Primzahl) |
Für große Zahlen (Hunderte von Ziffern) ist die Versuchsteilung rechnerisch unmöglich.Miller-Rabin-Primalitätstest(probabilistisch, verwendet in der Kryptographie) und dieAKS-Primalitätsprüfung(deterministische Polynomzeit, 2002) verwendet werden.
Primärfaktorisierung
Jede zusammengesetzte Zahl kann als einzigartiges Produkt von Primzahlen geschrieben werden - ihre Primfaktorisierung. Dies wird durch den Grundsatz der Arithmetik garantiert.
| Zahl | Primfaktorisierung | Aufschlüsselung des Faktorbaums |
|---|---|---|
| 12 | 22 mal 3 | 12 -> 4x3 -> 2x2x3 |
| 60 | 22 x 3 x 5 | 60 -> 4x15 -> 22x3x5 |
| 100 bis 100 | 22 x 52 | 100 -> 4x25 -> 22x52 |
| 360 | 23 x 32 x 5 | 360 -> 8x45 -> 23x32x5 |
| 1 024 | 210 | Alle Primfaktoren sind 2. |
| 2.310 | 2 x 3 x 5 x 7 x 11 | Produkt der ersten 5 Primzahlen |
Die Primfaktorisierung wird verwendet, um den größten gemeinsamen Teiler (GCD) und das kleinste gemeinsame Vielfache (LCM) von Zahlen zu finden. GCD ((12, 18) = 22 x 3? Nein - nehmen Sie die minimale Potenz der gemeinsamen Primzahlen: GCD = 21 x 31 = 6. LCM nimmt die maximale Potenz: LCM ((12, 18) = 22 x 32 = 36.
Warum Primzahlen wichtig sind: Anwendungen in Mathematik und Technologie
Primzahlen sind die "Atome" der Arithmetik - der Grundsatz der Arithmetik besagt, dass jede positive ganze Zahl größer als 1 entweder prim ist oder als einzigartiges Produkt von Primzahlen ausgedrückt werden kann. Diese Einzigartigkeit macht Primzahlen zu den unreduzierbaren Bausteinen aller Zahlen.
Moderne Internetsicherheithängt von Primzahlen ab. Die RSA-Verschlüsselung (verwendet für HTTPS, E-Mail-Verschlüsselung und digitale Signaturen) erzeugt öffentliche Schlüssel durch Multiplikation zweier großer Primzahlen p und q, um n = p x q zu bilden. Verschlüsselungs- und Entschlüsselungsschlüssel werden mit modularer Arithmetik mit n berechnet.Faktorisierungsproblem für ganze Zahlen: angesichts von n (einer 2048-Bit-Zahl mit ~ 617 Dezimalziffern) ist das Finden von p und q mit der aktuellen Technologie rechnerisch unmöglich.
Diffie-Hellman-SchlüsselwechselWenn Sie sich über HTTPS mit einer Website verbinden, schützen Primzahlen Ihre Daten still und in Echtzeit.
Hash-TabellenWenn eine Hash-Funktion Schlüssel zu Bucket-Indizes abbildet, sorgt die Verwendung einer Primzahl von Buckets für eine bessere Verteilung, da Primzahlen keine Faktoren haben, die systematische Kollisionsmuster erzeugen könnten.
PseudorandomzahlengeneratorenDie Periode (vor der Wiederholung) solcher Generatoren ist oft gleich dem Primärmodul minus 1.
Besondere Arten von Prämien
Innerhalb der unendlichen Menge der Primzahlen haben bestimmte Teilmengen besondere Eigenschaften oder Bedeutung:
| Typ | Definition | Beispiele |
|---|---|---|
| Zwillingsprimzahlen | Prämien, die sich um 2 unterscheiden | In diesem Fall wird der Betrag der Vergütung in der Höhe der Vergütung festgesetzt, die der Betrag der Vergütung entspricht. |
| Mersennische Primzahlen | Prämien des Formulars 2n - 1 | 3., 7., 31., 127., 8. 191 |
| Fermat-Primzahlen | Prämien der Form 2^(2n) + 1 | 3., 5., 17., 257, 65.537 |
| Sophie Germain Primzahlen | p und 2p+1 sind beide Primzahlen | 2, 3, 5, 11, 23 und 29 |
| Palindromische Primzahlen | Prämien, die nach vorne/nach hinten gleich aussehen | 11, 101, 131, 151, 181 |
| Sichere Primzahlen | Primzahlen p, wobei (p-1) / 2 auch prim ist | 5, 7, 11, 23, 47, 59 |
Mersennische Primzahlen(2n - 1) sind besonders wichtig, weil sie mit dem effizienten Lucas-Lehmer-Test auf Primalität getestet werden können. Das GIMPS-Projekt (Great Internet Mersenne Prime Search) nutzt verteilte Rechner weltweit, um neue Mersenne-Primzahlen zu finden. Ab 2024 ist die größte bekannte Mersenne-Primzahl 2^136,279,841 - 1, mit über 41 Millionen Dezimalziffern.
ZwillingsprimzahlenIm Jahr 2013 bewies Yitang Zhang das schwächere Ergebnis, dass es unendlich viele Primpaare gibt, die sich höchstens um 70 Millionen unterscheiden, was später auf 246 verbessert wurde.
Verteilung der Primzahlen
Primzahlen werden weniger häufig, wenn die Zahlen größer werden, aber ihre Verteilung folgt statistischen Mustern, die durch den Primzahlensatz beschrieben werden:
DiePrimzahlensatz(unabhängig von Hadamard und de la Vallée-Poussin im Jahr 1896 bewiesen) besagt, dass die Anzahl der Primzahlen bis N, bezeichnet als π ((N), für großes N ungefähr N / ln ((N) ist:
| N | Tatsächliche π(N) | Ungefähr N/ln (N) | Dichte |
|---|---|---|---|
| 100 bis 100 | 25 | 21.7 | 1 von 4 |
| 1000 t | 168 | 144,8 | 1 von 6 |
| 10 000 t | 1.229 | 1.085,7 | 1 von 8 |
| 100.000 Einheiten | 9.592 | 8.685,9 | 1 von 10 |
| 1 Million | 78.498 | 72.382,4 | 1 von 13 |
| 1.000.000.000 Einheiten | 50.847.534 | 48.254.942 | 1 von 20 |
DieRiemann-Hypothese- eines der Millennium Prize-Probleme mit einer Belohnung von 1 Million Dollar - betrifft die genaue Verteilung von Primzahlen. Es vermutet, dass alle nicht-trivialen Nullen der Riemann-Zeta-Funktion einen realen Teil 1/2 haben. Dies hängt damit zusammen, wie "zufällig" die Verteilung von Primzahlen erscheint - die Hypothese prognostiziert optimale Regelmäßigkeit in Primzahlenlücken.
Häufig gestellte Fragen
Ist 1 eine Primzahl?
Nein. Nach moderner mathematischer Konvention ist 1 weder einfach noch zusammengesetzt. 1 von Primzahlen auszuschließen bewahrt die Einzigartigkeit der Primfaktorisierung (der Grundsatz der Arithmetik) - wenn 1 einfach wäre, hätte jede Zahl unendlich viele Faktorisierungen (z. B. 6 = 2x3 = 1x2x3 = 1x1x2x3 = ...). Historisch betrachteten einige Mathematiker 1 einfach, aber die moderne Definition schließt es aus.
Was ist die größte bekannte Primzahl?
Ab 2024 ist die größte bekannte Primzahl 2^136,279,841 - 1 (eine Mersenne-Primzahl), die im Oktober 2024 entdeckt wurde. Sie hat über 41 Millionen Ziffern.
Gibt es Muster in Primzahlen?
Primes erscheinen unregelmäßig, aber Muster existieren. Alle Primzahlen > 5 enden mit 1, 3, 7 oder 9 (nie 0, 2, 4, 5, 6, 8). Alle Primzahlen > 3 haben die Form 6k+/-1. Zwillingsprimes (die sich um 2, wie 11 und 13 unterscheiden) scheinen für immer fortzufahren (unbewiesene Zwillingsprimeschätzung).
Ist 2 eine Primzahl?
Ja, 2 ist eine Primzahl - und es ist die einzige gerade Primzahl. 2 hat genau zwei Faktoren (1 und 2), die die Definition erfüllen. Jede andere gerade Zahl ist durch 2 teilbar, was sie zusammengesetzt macht. Die Primheit von 2 ist ein besonderer Fall, der oft separat in Algorithmen und Beweisen behandelt werden muss.
Wie wird die Primalität in der Verschlüsselung verwendet?
Die RSA-Verschlüsselung erzeugt ein Schlüsselpaar durch: (1) Auswahl zweier großer Primzahlen p und q (jeweils 1024+ Bits), (2) Berechnung von n = pxq, (3) Ableitung des Verschlüsselungsschlüssels e und des Entschlüsselungsschlüssels d unter Verwendung modularer Arithmetik. Jeder kann mit n und e (öffentlicher Schlüssel) verschlüsseln, aber nur der Inhaber von p und q (oder d) kann entschlüsseln.
Wie kann man am schnellsten herausfinden, ob eine Zahl prim ist?
Für kleine Zahlen (bis ~10^12): optimierte Versuchsabteilung, die nur bis √n mit dem Muster 6k+/-1 überprüft. Für mittlere Zahlen: Miller-Rabin-Primaltest mit wenigen Zeugen ist probabilistisch, aber extrem schnell. Für sehr große Zahlen (kryptografische Größen, 1000+ Ziffern): probabilistische Tests wie Miller-Rabin mit vielen zufälligen Zeugen oder der AKS-Test für einen deterministischen Beweis.
Was ist eine Prime-Lücke?
Eine Primlücken ist die Differenz zwischen zwei aufeinanderfolgenden Primzahlen. Die kleinste Primlücken ist 1 (zwischen 2 und 3), und alle anderen aufeinanderfolgenden Primzahlen haben Lücken von mindestens 2 (da man ungerade sein muss). Lücken wachsen langsam im Durchschnitt: in der Nähe von N, ist die durchschnittliche Lücke zwischen Primzahlen ln(N). Außergewöhnlich große Primlücken existieren - es gibt willkürlich lange Sequenzen von aufeinanderfolgenden zusammengesetzten Zahlen (n! + 2, n! + 3, ..., n! + n sind alle zusammengesetzt für jede n).
Was sind die Primfaktoren von 100?
100 = 2 x 50 = 2 x 2 x 25 = 2 x 2 x 5 x 5 = 22 x 52. Die Primfaktoren von 100 sind 2 und 5. Diese Faktorisierung erklärt, warum 100 gleichmäßig durch 1, 2, 4, 5, 10, 20, 25, 50 und 100 geteilt wird - jeder Teiler entspricht einer Kombination von 20 1 2 und 50 1 2.
Was ist Goldbachs Vermutung?
Goldbachs Vermutung (1742) besagt, dass jede gerade ganze Zahl größer als 2 als Summe zweier Primzahlen ausgedrückt werden kann. Zum Beispiel: 4=2+2, 6=3+3, 8=3+5, 10=3+7, 100=3+97=11+89=17+83. Es wurde bis zu 4x10^18 rechnerisch verifiziert, bleibt aber nicht bewiesen. Es ist eines der ältesten und berühmtesten ungelösten Probleme in der Zahlentheorie.
Wie viele Primzahlen gibt es?
Es gibt unendlich viele Primzahlen - Euklid bewies dies um 300 v. Chr. Der Beweis durch Widerspruch: Wenn Primzahlen endlich wären, wäre ihr Produkt plus 1 entweder prim oder hätte einen Primfaktor, der nicht in der angeblichen vollständigen Liste wäre, ein Widerspruch. Während Primzahlen bei größeren Zahlen weniger dicht werden, hören sie nie auf. Es gibt genau 78.498 Primzahlen unter 1.000.000 und 5.761.455 Primzahlen unter 100.000.000.
Primzahlen in der Zahlentheorie und ungelöste Probleme
Die Primzahlen liegen im Zentrum einiger der schönsten und hartnäckigsten ungelösten Probleme der Mathematik. Das Verstehen dieser offenen Fragen verdeutlicht, wie viel wir über Primzahlen wissen - und wie viel trotz jahrhundertelanger Bemühungen geheimnisvoll bleibt.
Die Riemann-Hypothese (1859):Die Riemann-Zeta-Funktion ζ(s) = Σ(1/ns) verbindet sich mit der Verteilung von Primzahlen durch ihre Nullen. Die Hypothese besagt, dass alle nicht-trivialen Nullen auf der kritischen Linie liegen Re(s) = 1/2. Wenn es wahr ist, würde es die möglichst genaue Beschreibung liefern, wie Primzahlen verteilt sind. Über 10 Billionen Nullen wurden berechnet und alle liegen auf der kritischen Linie - aber es gibt keinen Beweis.
Zwillings-Prämie-Annahme:Gibt es unendlich viele Primzahlenpaare (p, p+2) - wie (11,13), (17,19), (41,43), (101,103)? Die Vermutung sagt ja, aber sie bleibt unbewiesen. Im Jahr 2013 bewies Yitang Zhangs Durchbruch, dass es unendlich viele Primzahlenpaare mit einer Lücke von höchstens 70 Millionen gibt - eine erste endliche Grenze. Das Polymath-Projekt reduzierte diese Grenze anschließend auf 246, was bedeutet, dass wir wissen, dass es unendlich viele Primzahlenpaare mit einer Lücke <= 246 gibt. Die Lücke von 2 bleibt unbewiesen.
Goldbachs Vermutung (1742):Jede gerade ganze Zahl größer als 2 ist die Summe zweier Primzahlen. Berechnungsweise bis zu 4 x 10^18 überprüft. Jede gerade Zahl, die bisher versucht wurde, erfüllt sie - oft in vielerlei Hinsicht (100 = 3+97 = 11+89 = 17+83 = 29+71 = 41+59 = 47+53). Dennoch deckt kein Beweis alle geraden Zahlen ab. Die "schwache Goldbach-Vermutung" (jede ungerade Zahl >= 7 ist die Summe von drei Primzahlen) wurde 2013 von Harald Helfgott bewiesen.
Mersenne-Primzahlen und perfekte Zahlen:Eine Mersenne-Primzahl ist eine der Formen 2n - 1 (wobei n selbst eine Primzahl sein muss). Die ersten sind: 3, 7, 31, 127, 8,191. Bis 2024 sind nur 52 bekannt. Mersenne-Primzahlen sind mit perfekten Zahlen verbunden: Jede Mersenne-Primzahl erzeugt eine gerade perfekte Zahl über die Formel 2 ^ ((p-1) x (2 ^ p - 1). Die Zahl 28 = 4 x 7 (mit Mersenne-Primzahl 7) und 496 = 16 x 31 (mit Mersenne-Primzahl 31) sind perfekte Zahlen. Gibt es unendlich viele Mersenne-Primzahlen? Unbekannt.
Die ABC-Annahme und ihre Implikationen:Die ABC-Vermutung (ausgesprochen 1985) ist eine tiefe Beziehung über die Primfaktorisierungen von drei Zahlen a + b = c. Wenn sie bewiesen wird, würde sie den Letzten Satz von Fermat und viele andere Ergebnisse als einfache Konsequenzen implizieren.
Die Primzahlen bleiben das ultimative mathematische Geheimnis: einfach zu definieren (eine Zahl mit exakt zwei Faktoren), doch ihre Verteilung ist komplex genug, um offenen Problemen zugrunde zu liegen, die den größten mathematischen Köpfen seit Jahrhunderten widerstanden haben. Jeder neue Primzahlenrekord, jeder computergestützte Nachweis einer Vermutung auf eine neue Grenze, und jeder partielle Beweis fördert unser Verständnis - und erinnert uns daran, wie viel mehr es zu entdecken gibt.