Primfaktorzerlegungsrechner

Ueber die Primfaktorzerlegung

Die Primfaktorzerlegung ist der Prozess, eine positive ganze Zahl in ein Produkt von Primzahlen zu zerlegen. Jede ganze Zahl groesser als 1 kann als eindeutiges Produkt von Primzahlen geschrieben werden, ein Ergebnis, das als Fundamentalsatz der Arithmetik bekannt ist. Zum Beispiel: $360 = 2^3 \times 3^2 \times 5$.

Dieser Rechner zerlegt jede ganze Zahl von 2 bis 1.000.000.000 in ihre Primfaktoren, zeigt einen interaktiven Faktorbaum an, berechnet die Anzahl der Teiler, die Teilersumme und die Eulersche Phi-Funktion. Gib eine zweite Zahl ein, um auch den groessten gemeinsamen Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) zu berechnen.

Der Fundamentalsatz der Arithmetik

Jede ganze Zahl n > 1 kann eindeutig (bis auf die Reihenfolge) als Produkt von Primzahlpotenzen dargestellt werden:

wobei $p_1 < p_2 < \cdots < p_k$ verschiedene Primzahlen sind und jeder Exponent $a_i \geq 1$. Diese Eindeutigkeit macht die Primfaktorzerlegung zur Grundlage vieler Bereiche der Mathematik, vom Kuerzen von Bruechen bis zur modernen Kryptographie.

So verwendest du diesen Rechner

Einzelzahlmodus

Gib eine beliebige ganze Zahl zwischen 2 und 1.000.000.000 ein. Der Rechner zeigt sofort die Primfaktorzerlegung in Exponentialschreibweise, einen interaktiven Faktorbaum, alle Teiler und zahlentheoretische Eigenschaften an.

Zweizahlmodus (ggT & kgV)

Gib eine zweite Zahl ein, um den groessten gemeinsamen Teiler und das kleinste gemeinsame Vielfache zu berechnen. Ein Venn-Diagramm veranschaulicht, welche Primfaktoren gemeinsam und welche exklusiv fuer jede Zahl sind.

Schrittweise Division

Aktiviere Divisionsschritte anzeigen, um die Probedivision nachzuverfolgen: Jede Zeile zeigt den getesteten Teiler, den resultierenden Quotienten und den Rest.

Den Faktorbaum lesen

Der Faktorbaum teilt jede zusammengesetzte Zahl in ihren kleinsten Primteiler und den Quotienten auf und wiederholt dies, bis alle Zweige bei Primzahlen enden. Fuer eine ausfuehrliche Erklaerung, den Fundamentalsatz der Arithmetik und den Probedivisionsalgorithmus siehe den Faktorbaum-Leitfaden.

Formeln und Methoden

Probedivision ($6k \pm 1$)

Der Algorithmus dividiert zuerst wiederholt durch 2 und 3 und testet dann Kandidaten der Form $6k-1$ und $6k+1$ bis $\sqrt{n}$. Dies ueberspringt alle Vielfachen von 2 und 3 und reduziert die Anzahl der Tests um etwa 2/3. Zeitkomplexitaet: $O(\sqrt{n})$ — maximal 31.623 Iterationen fuer die maximale Eingabe von $10^9$.

Teileranzahl und Teilersumme

$d(n) = \prod (a_i + 1)$ zaehlt die Teiler; $\sigma(n)$ summiert sie mithilfe einer geometrischen Reihenformel. Fuer die vollstaendigen Formeln, vollkommene Zahlen und den Satz von Euklid-Euler siehe den Teilerrechner-Leitfaden.

Eulersche Phi-Funktion $\phi(n)$

Zaehlt die ganzen Zahlen in [1, n], die teilerfremd zu n sind. Fuer eine Primzahl $p$ gilt $\phi(p) = p - 1$. Fuer den Satz von Euler, die RSA-Kryptographie und Rechenbeispiele siehe den Euler-Phi-Funktionsrechner-Leitfaden.

ggT und kgV ueber Faktorisierung

Der ggT nimmt gemeinsame Primfaktoren mit dem jeweils kleineren Exponenten; das kgV nimmt alle Primfaktoren mit dem jeweils groesseren Exponenten. Fuer die Grundidentitaet, praktische Beispiele und Planungsprobleme siehe den ggT/kgV-Rechner-Leitfaden.

Praxisbeispiele

1. Brueche kuerzen

Um 48/180 zu kuerzen, finde ggT(48, 180). Faktorisierung: $48 = 2^4 \times 3$, $180 = 2^2 \times 3^2 \times 5$. $\gcd = 2^2 \times 3 = 12$. Teile beide durch 12: $48/180 = 4/15$.

2. Planungsprobleme

Zwei Busse kommen alle 12 und 18 Minuten. Wann treffen sie zusammen? $\text{kgV}(12, 18)$: $12 = 2^2 \times 3$, $18 = 2 \times 3^2$. $\text{kgV} = 2^2 \times 3^2 = 36$ Minuten.

3. Zahnradverhaeltnisse vereinfachen

Zahnraeder mit 24 und 36 Zaehnen. ggT(24, 36) = 12. Einfachstes Verhaeltnis: 2:3.

Eulersche Phi-Funktion und RSA-Kryptographie

Die Eulersche Phi-Funktion ist das mathematische Rueckgrat der RSA-Verschluesselung, des am weitesten verbreiteten Public-Key-Kryptosystems. Fuer den vollstaendigen RSA-Schluesselerzeugungsprozess, den Satz von Euler und die Sicherheitsanalyse siehe den Euler-Phi-Funktionsrechner-Leitfaden.

Haeufige Missverstaendnisse

• 1 ist keine Primzahl. Per Konvention ist 1 weder prim noch zusammengesetzt. Wuerde man 1 als prim einschliessen, waere die Eindeutigkeit der Faktorisierung gebrochen.
• Nicht alle ungeraden Zahlen sind prim. Beispiele: $9 = 3^2$, $15 = 3 \times 5$, $21 = 3 \times 7$.
• Primzahlen sind unendlich. Euklid bewies, dass keine endliche Liste von Primzahlen vollstaendig sein kann.
• Faktorisierung ist nicht dasselbe wie das Auflisten von Faktorpaaren. Die Primfaktorzerlegung ergibt die eindeutige kanonische Form; Faktorpaare (z. B. $12 = 3 \times 4 = 2 \times 6$) sind nicht eindeutig.

Algorithmusleistung

Dieser Rechner verwendet Probedivision mit $6k \pm 1$-Optimierung, die in $O(\sqrt{n})$ laeuft. Fuer die maximale Eingabe von $10^9$ testet der Algorithmus hoechstens $\sqrt{10^9} \approx 31{,}623$ Kandidaten und beendet die Berechnung in weit unter 100ms in jedem modernen Browser. Keine serverseitige Berechnung ist erforderlich.

Fuer Zahlen deutlich groesser als $10^{12}$ werden fortgeschrittene Algorithmen wie das Quadratische Sieb oder das Allgemeine Zahlkoerpersieb benoetigt, die jedoch den Rahmen eines browserbasierten Lernwerkzeugs sprengen.

Haeufig gestellte Fragen

Was ist eine Primzahl?

Eine Primzahl ist eine natuerliche Zahl groesser als 1, die keine positiven Teiler ausser 1 und sich selbst hat. Die ersten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Wie funktioniert der Faktorbaum?

Der Baum beginnt mit deiner Zahl an der Spitze. Auf jeder Ebene wird die Zahl in ihren kleinsten Primfaktor (linker Zweig) und den verbleibenden Quotienten (rechter Zweig) aufgeteilt. Dies wird fortgesetzt, bis alle Zweige in Primzahlen enden.

Wofuer wird der ggT verwendet?

Der groesste gemeinsame Teiler wird zum Kuerzen von Bruechen, zum Finden gemeinsamer Nenner, zum Loesen diophantischer Gleichungen und im euklidischen Algorithmus verwendet. Er ist einer der aeltesten Algorithmen der Mathematik.

Warum kann ich keine Zahlen groesser als 1 Milliarde eingeben?

Die Laufzeit der Probedivision waechst mit $\sqrt{n}$. Fuer $10^9$ sind das etwa 31.000 Schritte (sofort). Fuer $10^{18}$ waeren etwa $10^9$ Schritte noetig, was den Browser einfrieren koennte. Die Obergrenze sorgt fuer gleichbleibende Leistung.

Was ist der Unterschied zwischen Primfaktorzerlegung und dem Auflisten von Teilern?

Die Primfaktorzerlegung drueckt eine Zahl als Produkt von Primzahlen aus (z. B. $12 = 2^2 \times 3$). Das Auflisten der Teiler gibt alle Teiler an (1, 2, 3, 4, 6, 12). Dieser Rechner zeigt beides.

Hat die Primfaktorzerlegung etwas mit Kryptographie zu tun?

Ja. Die RSA-Verschluesselung beruht auf der Schwierigkeit, grosse Halbprimzahlen (Produkte zweier grosser Primzahlen) zu faktorisieren. Waehrend dieser Rechner Zahlen bis $10^9$ problemlos verarbeitet, wuerde die Faktorisierung einer 2048-Bit-Halbprimzahl mit aktueller Technologie Milliarden von Jahren dauern.

Quellenangaben

• Wikipedia. “Fundamentalsatz der Arithmetik.” https://de.wikipedia.org/wiki/Fundamentalsatz_der_Arithmetik
• Wolfram MathWorld. “Fundamental Theorem of Arithmetic.” https://mathworld.wolfram.com/FundamentalTheoremofArithmetic.html
• Wikipedia. “Probedivision.” https://de.wikipedia.org/wiki/Probedivision
• Wikipedia. “Sieb des Eratosthenes.” https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
• Wikipedia. “Ganzzahl-Faktorisierung.” https://de.wikipedia.org/wiki/Faktorisierungsverfahren

Haftungsausschluss

Dieser Rechner wird zu Bildungszwecken bereitgestellt. Obwohl die Algorithmen fuer alle gueltigen Eingaben mathematisch korrekt sind, ist dieses Werkzeug nicht fuer kryptographische Anwendungen vorgesehen. Fuer produktive Kryptographie verwende etablierte Bibliotheken mit Constant-Time-Implementierungen.