Primfaktorzerlegung

Berechnungen Vergleichen

Downloads

Enthält Ihre Eingaben und Ergebnisse für diese Berechnung sowie alle zusätzlichen Berechnungen, die Sie verglichen haben.

Wie eine Zahl in ihre Prim-Bausteine Zerlegt Wird

Jede ganze Zahl größer als 1 kann in eine eindeutige Menge von miteinander multiplizierten Primzahlen zerlegt werden — ihre Primfaktorzerlegung. Geben Sie eine ganze Zahl ein, und dieser Rechner findet diese Zerlegung sofort, zusammen mit der Information, ob die Zahl selbst eine Primzahl ist.

Die Formel

Der Fundamentalsatz der Arithmetik garantiert, dass jede ganze Zahl N größer als 1 genau eine Primfaktorzerlegung hat, bis auf die Reihenfolge, in der die Faktoren geschrieben werden:

\vA{N} = \vB{p_1}^{\vC{a_1}} \times \vB{p_2}^{\vC{a_2}} \times \cdots \times \vB{p_k}^{\vC{a_k}}

wobei jedes $\vB{p_i}$ eine verschiedene Primzahl ist und jedes $\vC{a_i}$ angibt, wie oft diese Primzahl gleichmäßig in N aufgeht.

Dieser Rechner findet diese Zerlegung mittels Probedivision: Beginnend bei 2, prüft er wiederholt, ob jede Zahl gleichmäßig in den verbleibenden Rest aufgeht, teilt sie heraus (und zählt, wie oft), wenn dies der Fall ist, und geht dann zum nächsten Kandidaten über. Sobald das Quadrat eines Kandidaten den Rest übersteigt, muss alles, was noch übrig bleibt, selbst eine Primzahl sein — jeder kleinere Faktor wäre bereits gefunden worden:

\text{wenn } \vD{d}^2 > \vE{\text{verbleibender Wert}}, \text{ dann ist } \vE{\text{verbleibender Wert}} \text{ eine Primzahl}

Beispielrechnung

Die Primfaktorzerlegung von 360 finden:

360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45 (2 geht 3-mal auf; 45 ist ungerade, also weiter).
45 ÷ 3 = 15, ÷ 3 = 5 (3 geht 2-mal auf; 5 ist nicht erneut durch 3 teilbar).
5 bleibt übrig, und kein weiterer Divisor hat ein Quadrat ≤ 5, also ist 5 selbst eine Primzahl.
Ergebnis: 2³ × 3² × 5.

Wichtige Einflussfaktoren

Jede Primfaktorzerlegung ist eindeutig — genau das garantiert der Fundamentalsatz der Arithmetik. Egal wie eine Zahl zerlegt wird, ihre Primfaktorzerlegung kommt immer gleich heraus (abgesehen von der Reihenfolge, in der die Faktoren geschrieben werden), weshalb die Primfaktorzerlegung ein derart fundamentaler Baustein in der gesamten Zahlentheorie ist.
Die Primfaktorzerlegung ist der Mechanismus hinter dem Auffinden eines größten gemeinsamen Teilers oder kleinsten gemeinsamen Vielfachen von Hand. Der direkte Vergleich der Primfaktorzerlegungen zweier Zahlen zeigt direkt ihren GGT (die gemeinsamen Primfaktoren, beim niedrigeren gemeinsamen Exponenten) und ihr KGV (jeder Primfaktor, beim höheren Exponenten) — siehe den GGT-/KGV-Rechner für diesen konkreten Vergleich.
Das Faktorisieren großer Zahlen wird rechnerisch mit wachsender Ziffernzahl weit schwieriger, was die Grundlage für manche Verschlüsselungsmethoden ist. Probedivision (die hier verwendete Methode) funktioniert gut für Zahlen, die Menschen typischerweise von Hand eingeben, aber das Faktorisieren einer sehr großen Zahl mit Hunderten von Ziffern kann selbst für leistungsstarke Computer rechnerisch unmöglich sein — genau diese Schwierigkeit liegt der Sicherheit der RSA-Verschlüsselung zugrunde.
Eine Primzahl hat genau einen Primfaktor: sich selbst, zur ersten Potenz. Deshalb ergibt sich die „ist diese Zahl eine Primzahl”-Prüfung dieses Rechners direkt aus dem Faktorisierungsprozess — wenn die Probedivision nie einen Faktor kleiner als die eigene Quadratwurzel der Zahl findet, hat die Zahl keine andere Zerlegung als sich selbst.

Häufige Fehler

Primfaktorzerlegung mit einer vollständigen Liste aller Teiler verwechseln. Die Teiler von 12 sind 1, 2, 3, 4, 6 und 12, aber ihre Primfaktorzerlegung ist nur 2² × 3 — die Primfaktorzerlegung behält nur die Primbausteine, nicht jede Zahl, die glatt aufgeht.
1 als Primzahl behandeln. Per Definition hat eine Primzahl genau zwei verschiedene Teiler (1 und sich selbst) — 1 hat nur einen, ist also weder Primzahl noch zusammengesetzte Zahl und erscheint niemals in einer Primfaktorzerlegung.
Den Überblick über wiederholte Primfaktoren verlieren. Die Primfaktorzerlegung von 8 ist 2³, nicht nur „2” — zu vergessen, wie oft eine Primzahl aufgeht, ändert die Zahl, die die Zerlegung tatsächlich darstellt.

Gut zu Wissen

Benötigen Sie den größten gemeinsamen Teiler oder das kleinste gemeinsame Vielfache zweier Zahlen statt der eigenen Faktoren einer Zahl? Rechner für ggT und kgV vergleicht direkt die Primfaktorzerlegungen zweier Zahlen.
Kürzen Sie einen Bruch auf seine einfachste Form? Bruchrechner verwendet dieselben gemeinsamen Primfaktoren, die dieser Rechner findet.
Arbeiten Sie stattdessen mit einer sehr großen oder sehr kleinen Zahl? Rechner für wissenschaftliche Notation rechnet zwischen Standard- und wissenschaftlicher Schreibweise um.

Quelle: Probedivision.

Häufig Gestellte Fragen

Was ist Primfaktorzerlegung?

Die Primfaktorzerlegung zerlegt eine ganze Zahl in die Primzahlen, die miteinander multipliziert sie ergeben — jede ganze Zahl größer als 1 hat genau eine solche Zerlegung (der „Fundamentalsatz der Arithmetik“). Zum Beispiel ist 12 = 2 × 2 × 3.

Woher weiß ich, ob eine Zahl eine Primzahl ist?

Eine Primzahl hat keine anderen Faktoren als 1 und sich selbst. Die Zerlegung dieses Rechners zeigt genau diese eine Zahl (ohne andere Faktoren), wenn die von Ihnen eingegebene Zahl eine Primzahl ist — der Analyse-Abschnitt vermerkt dies direkt.

Gibt es eine Grenze, wie groß eine Zahl sein kann, die ich zerlegen kann?

Dieser Rechner verwendet Probedivision, die für den Bereich von Zahlen gut funktioniert, den ein typischer Anwendungsfall umfasst, aber bei extrem großen Zahlen (der Art, die in der Kryptografie verwendet werden) langsam wird, welche weitaus ausgefeiltere Algorithmen benötigen.