DE

Primfaktorzerlegung und Primzahltest online

Eine ganze Zahl genügt, um zu erfahren, ob sie eine Primzahl ist, ihre Primfaktorzerlegung zu erhalten und die Liste ihrer Teiler. Eine Primzahl hat nur zwei Teiler : 1 und sich selbst — ihre Zerlegung besteht dann aus einem einzigen Faktor mit Exponent 1.

Rechner

Ganze Zahl

Zwischen 2 und 1 Milliarde.

Ergebnisse

Ist — eine Primzahl? —
Primfaktorzerlegung —
Anzahl positiver Teiler —
Summe der Teiler —
Liste der Teiler —

Wie eine Primfaktorzerlegung berechnet wird

Probedivision durch 2, 3, 5, 7… bis √n: jeder gefundene Teiler ist ein Primfaktor

Anzahl der Teiler = Produkt aus (Exponent + 1) jedes Primfaktors

Es genügt, die Teiler bis zur Quadratwurzel von n zu testen : teilt kein Primfaktor kleiner oder gleich √n die Zahl n, dann ist n eine Primzahl — jeder Teiler darüber hätte einen bereits getesteten, kleineren „Partner“. Die Gesamtzahl der Teiler ergibt sich direkt aus den Exponenten der Zerlegung, ohne dass man sie alle aufzählen müsste.

Ein Asterisk hinter einem Begriff verweist auf das Glossar am Seitenende.

Was eine Primzahl ist — und was nicht

Eine ganze Zahl größer als 1 ist eine Primzahl*, wenn sie genau zwei positive Teiler hat: 1 und sich selbst. Kein Produkt zweier kleinerer ganzer Zahlen ergibt diese Zahl.

2, 3, 5, 7, 11, 13, 17, 19, 23 — das ist der Anfang der Liste, den die meisten aus der Mittelstufe noch hersagen können. 4 gehört nicht dazu (2 × 2), 9 nicht (3 × 3), 15 nicht (3 × 5). Das sind zusammengesetzte Zahlen*. Ab 2 gibt es kein drittes Fach: prim oder zusammengesetzt.

Auf dieser Seite steht das in der Zerlegung. Ein einziger Faktor, Exponent 1? Dann ist die Zahl prim. Zwei Faktoren, oder ein Exponent größer als 1, und sie ist zusammengesetzt. 9 = 3² ist keine Primzahl — ein einzelner Primfaktor in der Anzeige reicht nicht, sobald die Potenz größer als 1 ist.

Warum 1 keine Primzahl ist

Die Frage kommt jedes Schuljahr. 1 ist nur durch 1 teilbar, warum also keine Primzahl?

Weil die Definition zwei verschiedene Teiler verlangt. 1 hat einen. Zusammengesetzt ist die 1 auch nicht: man zerlegt sie nicht in kleinere Ganze. Die Eins steht für sich. Der eigentliche Grund ist der Fundamentalsatz der Arithmetik*: jede ganze Zahl > 1 besitzt genau eine Primfaktorzerlegung, abgesehen von der Reihenfolge. Wäre 1 prim, könnte man jede Zerlegung mit beliebig vielen Einsen aufpolstern (1 × 1 × 5 = 5). Die Eindeutigkeit wäre weg. Also bleibt 1 draußen. Das ist keine Marotte der Schulbücher.

Das Formular nimmt nichts unter 2 an. Da gibt es schlicht nichts zu zerlegen.

Probedivision bis zur Quadratwurzel

Ob n prim ist, entscheidet ein endlicher Test: teilt irgendeine Primzahl p mit p² ≤ n die Zahl n? Falls ja, ist n zusammengesetzt. Falls nein, ist n prim. Jeder Teiler oberhalb von √n hätte einen Partner unterhalb — den hätte der Test schon gefunden.

Praktisch beginnt die Schleife bei 2 und arbeitet sich nach oben. Gerade Zahlen außer 2 fallen sofort. Danach bleiben die Ungeraden. 360 zerfällt so: durch 2 (mehrfach), durch 3 (mehrfach), durch 5, und der Rest ist 1. Ergebnis: 2³ × 3² × 5. 367 übersteht denselben Weg bis √367 ≈ 19,2 ohne Teiler — also prim.

Bis eine Milliarde bleibt √n unter etwa 31.623. Das schafft eine PHP-Schleife, bevor die Seite gerendert ist. Genau deshalb endet die Eingabe hier: eine Zerlegung zum Lesen, kein Angriff auf einen Kryptomodul.

Das Sieb des Eratosthenes

Für eine einzelne Zahl reicht die Probedivision bis √n. Sollen alle Primzahlen bis zu einer Grenze N gefunden werden, sieben.

  1. Die ganzen Zahlen von 2 bis N aufschreiben.
  2. 2 ist prim: alle Vielfachen streichen (4, 6, 8…).
  3. Die nächste ungestrichene Zahl, 3, ist prim: 6, 9, 12… streichen.
  4. Weiter mit 5, 7 und so fort, bis √N. Was ungestrichen bleibt, ist prim.

Das ist kein Einzeltest, das ist ein Durchlauf. Jede zusammengesetzte Zahl wird nur ein paarmal angefasst. Deshalb füllt ein Sieb eine Primzahltabelle bis in die Millionen, ohne Drama. Diese Seite tut das nicht und antwortet nur für ein n. Die fünfzig Millionen Primzahlen unter einer Milliarde zu erzeugen, nur weil 360 im Feld steht, wäre Verschwendung.

In Klasse 5 oder 6 taucht das Sieb oft als Gitter bis 100 auf. 25 Primzahlen bleiben stehen. Das ist derselbe Algorithmus wie in der Zahlentheorie, nur auf kariertem Papier.

Primfaktorzerlegung und der Fundamentalsatz

Jede ganze Zahl größer als 1 zerfällt eindeutig in ein Produkt von Primzahlen, bis auf die Reihenfolge der Faktoren. 360 = 2³ × 3² × 5, und keine andere Kombination von Primzahlen ergibt 360. Das ist der Fundamentalsatz, kein Rechentrick.

Aus der Zerlegung folgen Teileranzahl und Teilersumme, ohne die Teiler aufzuzählen. Hat n die Form p₁e₁ × p₂e₂ × …, dann gilt

Anzahl der Teiler = (e₁ + 1)(e₂ + 1)…

Summe der Teiler = Π (pe+1 − 1) / (p − 1)

Für 360: Exponenten 3, 2, 1, also (3+1)×(2+1)×(1+1) = 24 Teiler. Die Summe ist 1.176. Die Tabelle oben rechnet genau das. Bei mehr als 300 Teilern bleibt die Liste verborgen — hochzusammengesetzte Zahlen würden sonst den Schirm füllen, ohne dass jemand sie liest.

Dieselbe Zerlegung entscheidet über Teilbarkeit: 8 = 2³ teilt 360, 16 = 2⁴ nicht. Wer die Exponenten hat, zählt nach, statt elf Reste zu bilden.

Primzahlzwillinge und Mersenne-Zahlen

Primzahlzwillinge* liegen 2 auseinander: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31) und so weiter. Es gibt enorm große Paare. Ob es unendlich viele gibt, weiß niemand.

Eine Mersenne-Zahl* hat die Form 2p − 1. Damit das prim ist, muss p selbst prim sein — nötig, nicht hinreichend. 211 − 1 = 2047 = 23 × 89, und 11 ist prim. Warum der Aufwand? Weil fast jeder Rekord der „größten bekannten Primzahl“ eine Mersenne-Primzahl ist. Die Form erlaubt einen eigenen Test (Lucas–Lehmer), der die Probedivision alt aussehen lässt. GIMPS, ein Netz freiwilliger Rechner, jagt diese Rekorde seit den 1990ern. Dieser Rechner macht da nicht mit. 219 − 1 liegt noch unter der Milliarde; 231 − 1 schon lange nicht mehr.

Zwillinge und Mersenne-Zahlen lassen sich mit dem Formular anfassen. Einen Sonderbetrieb der Arithmetik sind sie nicht.

Vollkommene Zahlen

Eine Zahl ist vollkommen* (man sagt auch perfekt), wenn die Summe ihrer echten Teiler — aller Teiler außer ihr selbst — wieder sie ergibt.

6 = 1 + 2 + 3. 28 = 1 + 2 + 4 + 7 + 14. Danach 496, dann 8.128. Die Folge dünnt rasch aus. Jede gerade vollkommene Zahl hat die Gestalt 2p−1(2p − 1), sobald 2p − 1 eine Mersenne-Primzahl ist (Satz von Euklid–Euler). Eine ungerade vollkommene Zahl hat niemand gefunden. Bewiesen, dass es keine gibt, hat auch niemand. Beide Fragen — ungerade Vollkommene, unendlich viele gerade — sind offen. 6 und 28 stehen trotzdem in jedem Schulbuch der Mittelstufe, oft als Anekdote am Rand des Teilerkapitels.

Die Tabelle hier addiert alle Teiler, n eingeschlossen. Eine vollkommene Zahl zeigt deshalb die Teilersumme 2n. Bei 28 steht 56.

Wozu große Primzahlen dienen

In der Schule zerlegt man sie. Auf einem Rechner verstecken sie Information.

Die Public-Key-Kryptographie — der Name, den man kennt, ist RSA* — multipliziert zwei sehr große Primzahlen, n = p × q. Das Produkt ist billig. p und q aus n zurückzuholen, ohne sie zu kennen, liegt jenseits heutiger Mittel, sobald die Primzahlen ein paar hundert Stellen haben. Genau das ist der öffentliche Schlüssel: n darf offen liegen, die Faktoren nicht. Primzahlen tauchen außerdem als Größe von Hashtabellen auf (ein Primzahlmodul verteilt Kollisionen gleichmäßiger), in manchen Pseudozufallsgeneratoren, in fehlerkorrigierenden Codes. Immer dieselbe Idee: modulo einer Primzahl benimmt sich die Arithmetik anständig; das Produkt zweier großer Primzahlen lässt sich schlecht wieder auseinandernehmen.

Die Primzahlen dieser Seite haben mit einem Schlüssel nichts zu tun. Die Grenze liegt bei einer Milliarde — zehn Stellen, Mittelstufe. Ein üblicher RSA-Modul hat 2048 Bit, über 600 Stellen. 360 zu zerlegen bringt einer Schlüsselknackerei nicht näher.

Primzahltest für sehr große Zahlen

Bis eine Milliarde ist die Probedivision bis √n ehrlich: √1.000.000.000 liegt bei rund 31.623 Versuchen. Die Seite ist fertig, bevor jemand hinsehen kann.

Dieselbe Methode an einer 50-stelligen Zahl, und √n hat 25 Stellen. Auf 1025 Divisionen wartet niemand. Bei so großen Zahlen faktorisiert man nicht mehr, man startet einen Primzahltest (in der Praxis Miller–Rabin; andere Tests, wenn die Zahl eine hilfreiche Form hat). Der Test darf „prim“ sagen, ohne einen einzigen Faktor zu zeigen. Faktorisieren ist ein anderes, härteres Geschäft — darauf setzt RSA. Eine Zahl kann also als prim gelten, ohne dass jemand ihre Teiler aufgeschrieben hat, aus dem einfachen Grund, dass die Liste zwei Zeilen hat: 1 und sie selbst.

Primfaktoren, Brüche und der ggT

Einen Bruch kürzen heißt, das zu streichen, was Zähler und Nenner gemeinsam haben. Diese gemeinsamen Faktoren sind der ggT.

Ist a = 2³ × 3² × 5 und b = 2² × 3 × 7, nimmt der ggT den kleineren Exponenten jeder Primzahl: 2² × 3 = 12. Das kgV nimmt den größeren: 2³ × 3² × 5 × 7 = 2.520. 360/12 durch 84/12 ist der gekürzte Bruch 30/7. Den euklidischen Algorithmus braucht es nicht, wenn beide Zerlegungen schon da liegen — vorausgesetzt, die Zahlen sind klein genug, um sie überhaupt zu zerlegen.

Der ggT- und kgV-Rechner arbeitet andersherum, mit dem euklidischen Algorithmus, auch für eine ganze Liste. Die beiden Seiten gehören zur selben Arithmetik: eine Zahl zerlegen und mehrere Zahlen vergleichen, dasselbe Material, zwei Handgriffe.

Unendlich viele Primzahlen

Euklid zeigt das, ohne eine Formel für die nächste zu liefern.

Angenommen, es gäbe nur endlich viele: p1, p2, …, pk. Man bildet N = p1 × p2 × … × pk + 1. Keines der pi teilt N (Rest 1). Also ist N selbst prim — und fehlte in der Liste — oder N hat einen brandneuen Primfaktor. In beiden Fällen war die Liste unvollständig. Das Spiel lässt sich beliebig oft wiederholen. Wie die nächste Primzahl gefunden wird, steht nicht da. Nur, dass immer noch eine wartet.

N = (Produkt der vermeintlich letzten Primzahlen) + 1 → neue Primzahl oder neuer Faktor

Dichter werden sie nicht. Zwischen 1 und 100 stehen 25 Primzahlen, zwischen 1 und 1.000 stehen 168. Seltener heißt nicht letzte. Der Beweis taucht im Abitur selten als Rechenaufgabe auf; als Argument, das ohne Formel auskommt, gehört er zum Bild der Zahlentheorie, das ein Leistungskurs zeichnet.

Die Goldbachsche Vermutung

Jede gerade ganze Zahl größer als 2 wäre Summe zweier Primzahlen. 4 = 2+2, 6 = 3+3, 8 = 3+5, 10 = 3+7 = 5+5, und so weiter.

Rechner haben das bis in enorme Bereiche geprüft. Bewiesen ist es nicht. Es ist eine Vermutung, kein Satz — das gehört gesagt, auch wenn der Anspruch in einen Satz passt und nie ein Gegenbeispiel auftauchte. Eine schwächere Fassung (jede ungerade Zahl ≥ 7 ist Summe dreier Primzahlen) ist bewiesen. Die starke Form, die in der Schule erzählt wird, ist offen. Letztlich eines dieser Probleme, deren Formulierung kürzer ist als jede ehrliche Erklärung, warum man feststeckt.

Diese Seite prüft Goldbach nicht und zerlegt eine einzelne Zahl. Zur Übung lässt sich eine Gerade nehmen, zerlegen und zwei Primzahlen suchen, die sie wieder ergeben. Das ist kein Beweis.

2 ist die einzige gerade Primzahl

Jede gerade Zahl außer 2 ist durch 2 teilbar, also zusammengesetzt. 2 bleibt allein.

Das klingt nach Schulhof, und es kürzt viele Beweise. Jenseits von 2 sucht man nur noch unter den Ungeraden. Der erste Siebdurchgang streicht schon jedes zweite Feld: die Parität ist der gröbste Filter. Primzahlzwillinge sind fast immer zwei Ungerade im Abstand 2. Das Paar (2, 3) liegt nebeneinander, das sind keine Zwillinge.

Endet eine Zahl auf 0, 2, 4, 6 oder 8 und ist sie nicht 2, erübrigt sich der Primzahlgedanke. Die Teilbarkeitsregel für 2 reicht.

Glossar

Primzahl
Ganze Zahl größer als 1 mit genau zwei positiven Teilern: 1 und sich selbst. Die Folge beginnt 2, 3, 5, 7, 11, 13, …
Zusammengesetzte Zahl
Ganze Zahl größer als 1, die nicht prim ist — also Produkt kleinerer ganzer Zahlen. 4, 9, 15, 360 sind zusammengesetzt; 1 ist es nicht.
Fundamentalsatz der Arithmetik
Jede ganze Zahl größer als 1 besitzt genau eine Primfaktorzerlegung, abgesehen von der Reihenfolge der Faktoren. Deshalb zählt 1 nicht als Primzahl.
Primzahlzwillinge
Paar von Primzahlen im Abstand 2, etwa (17, 19). Ob unendlich viele existieren, ist unbewiesen.
Mersenne-Zahl
Zahl der Form 2p − 1. Prim kann sie nur sein, wenn p selbst prim ist; hinreichend ist das nicht. Fast alle Rekordprimzahlen sind Mersenne-Primzahlen.
Vollkommene Zahl
Positive ganze Zahl, die gleich der Summe ihrer echten Teiler ist. 6 und 28 sind die kleinsten. Gerade vollkommene Zahlen hängen an Mersenne-Primzahlen; ungerade sind unbekannt.
RSA
Public-Key-Verfahren, das auf dem Produkt zweier großer Primzahlen beruht. Das Produkt darf öffentlich sein; die Faktoren nicht. Die Zahlen dieser Seite (bis eine Milliarde) liegen weit unter kryptographischer Größe.

Das könnte Sie auch interessieren