Primfaktorzerlegung – Rechner

Zuletzt aktualisiert: 2026-05-19

Was ist Primfaktorzerlegung?

Jede ganze Zahl größer als 1 lässt sich als Produkt von Primzahlen schreiben. Diese Darstellung heißt Primfaktorzerlegung. Beispiel:

$360 = 2^3 \cdot 3^2 \cdot 5$

Die Primzahlen 2, 3 und 5 sind die „Atome" der 360 – sie lassen sich nicht weiter zerlegen. Die Exponenten (3, 2 und 1) geben an, wie oft jede Primzahl im Produkt vorkommt.

Der Fundamentalsatz der Arithmetik

Der Fundamentalsatz der Arithmetik garantiert zwei Dinge:

1. Existenz: Jede ganze Zahl größer als 1 besitzt mindestens eine Primfaktorzerlegung.
2. Eindeutigkeit: Diese Zerlegung ist – bis auf die Reihenfolge der Faktoren – eindeutig.

Warum ist 1 keine Primzahl? Würde man 1 als Primzahl zählen, gäbe es unendlich viele Primfaktorzerlegungen (360 = 1 · 2³ · 3² · 5 = 1² · 2³ · 3² · 5 usw.). Die Eindeutigkeit ist nur gesichert, wenn 1 ausgeschlossen wird.

Probedivision – so geht die Zerlegung

Die einfachste Methode ist die Probedivision: Teste alle Zahlen von 2 bis $\sqrt{n}$ als mögliche Teiler.

Schritt für Schritt für n = 360:

1. Durch 2 teilbar? Ja: 360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45. 45 ist ungerade, 2 geht nicht mehr. Faktor 2³.
2. Durch 3 teilbar? Ja: 45 ÷ 3 = 15, 15 ÷ 3 = 5. 5 ist nicht durch 3 teilbar. Faktor 3².
3. Durch 5 teilbar? Ja: 5 ÷ 5 = 1. Faktor 5¹.
4. Quotient ist 1 – fertig. Ergebnis: $360 = 2^3 \cdot 3^2 \cdot 5$.

Warum nur bis $\sqrt{n}$? Hat n einen Primfaktor p > $\sqrt{n}$, so ist n/p < $\sqrt{n}$, also muss auch ein kleinerer Faktor existieren. Wird bis $\sqrt{n}$ kein Teiler gefunden, ist n selbst eine Primzahl.

Primfaktorbaum

Ein Primfaktorbaum veranschaulicht die Zerlegung: Man teilt eine Zahl in beliebige zwei Faktoren und wiederholt das, bis alle Äste bei Primzahlen enden.

         360
        /    \
       8      45
      / \    /  \
     4   2  9    5
    / \    / \
   2   2  3   3

Die Blätter ergeben 2, 2, 2, 3, 3, 5 → 2³ · 3² · 5. Unabhängig davon, wie man den Baum aufbaut, kommt man stets zum gleichen Ergebnis – das ist die Eindeutigkeit in der Praxis.

Teileranzahl aus der Primfaktorzerlegung

Hat man die Primfaktorzerlegung, lässt sich die Anzahl der positiven Teiler mit einer einzigen Formel berechnen:

$\tau(n) = (e_1+1)(e_2+1)\cdots(e_k+1)$

Warum? Jeder Teiler von n entsteht, indem man für jede Primzahl $p_i$ einen Exponenten zwischen 0 und $e_i$ wählt – das sind $(e_i+1)$ Möglichkeiten pro Primzahl, und die Wahlen sind voneinander unabhängig.

Beispiel – Teiler von 360:

$\tau(360) = (3+1)(2+1)(1+1) = 4 \cdot 3 \cdot 2 = 24$

Die Zahl 360 hat genau 24 positive Teiler.

ggT und kgV aus der Primfaktorzerlegung

Kennt man die Zerlegungen zweier Zahlen, lassen sich ggT und kgV direkt ablesen:

• ggT: Wähle für jede Primzahl den kleineren Exponenten.
• kgV: Wähle für jede Primzahl den größeren Exponenten.

Beispiel: ggT und kgV von 360 und 504

$360 = 2^3 \cdot 3^2 \cdot 5, \qquad 504 = 2^3 \cdot 3^2 \cdot 7$

Primzahl	Exp. 360	Exp. 504	min (ggT)	max (kgV)
2	3	3	3	3
3	2	2	2	2
5	1	0	0	1
7	0	1	0	1

$\text{ggT}(360, 504) = 2^3 \cdot 3^2 = 72, \qquad \text{kgV}(360, 504) = 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$

Brüche kürzen

Um $\dfrac{a}{b}$ auf den kleinsten Term zu bringen, dividiert man Zähler und Nenner durch $\text{ggT}(a, b)$:

$\frac{360}{504} = \frac{360 \div 72}{504 \div 72} = \frac{5}{7}$

Anwendungen

Bereich	Verwendung
Kryptografie (RSA)	Sicherheit beruht auf der Schwierigkeit, das Produkt zweier großer Primzahlen zu faktorisieren
Hash-Tabellen	Primzahlgrößen minimieren Kollisionen
Codierungstheorie	Generatorpolynome für fehlerkorrigierende Codes
Musiktheorie	Reintonungsintervalle sind Verhältnisse von Zweierpotenzen und kleinen Primzahlen

Sonderfälle

• n = 2 (kleinste Primzahl): Zerlegung ist 2 selbst; genau 2 Teiler.
• n ist Primzahl: Ein einziger Primfaktor; Teileranzahl = 2.
• Primzahlpotenz (z. B. 1024 = 2¹⁰): Nur eine verschiedene Primzahl; Teileranzahl = 11.
• Hochzusammengesetzte Zahlen (360, 720, 1260 …): Haben unter allen Zahlen ähnlicher Größe die meisten Teiler.

Kurzübersicht

Begriff	Formel
Primfaktorzerlegung	$n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$
Anzahl verschiedener Primfaktoren	$\omega(n) = k$
Teileranzahl	$\tau(n) = \prod (e_i + 1)$
ggT zweier Zahlen	Produkt mit minimalen Exponenten
kgV zweier Zahlen	Produkt mit maximalen Exponenten
Identität	$\text{ggT}(a,b) \times \text{kgV}(a,b) = a \times b$

Häufig gestellte Fragen (FAQ)

Was ist die Primfaktorzerlegung?

Die Primfaktorzerlegung ist die Darstellung einer ganzen Zahl größer als 1 als Produkt von Primzahlen. Zum Beispiel: 360 = 2³ · 3² · 5. Der Fundamentalsatz der Arithmetik garantiert, dass diese Darstellung – bis auf die Reihenfolge der Faktoren – eindeutig ist.

Warum ist die Primfaktorzerlegung eindeutig?

Der Fundamentalsatz der Arithmetik besagt, dass jede ganze Zahl größer als 1 genau eine Primfaktorzerlegung besitzt (Reihenfolge der Faktoren ausgenommen). Diese Eindeutigkeit macht die Primfaktorzerlegung zur Grundlage von Teilbarkeit, ggT, kgV und vielen kryptografischen Verfahren wie RSA.

Wie berechnet man die Teileranzahl aus der Primfaktorzerlegung?

Ist n = p₁^e₁ · p₂^e₂ · … · pₖ^eₖ, so gilt τ(n) = (e₁+1)(e₂+1)…(eₖ+1). Für 360 = 2³ · 3² · 5¹ ergibt sich τ(360) = 4 · 3 · 2 = 24. Die Zahl 360 hat also genau 24 positive Teiler.

Wie groß darf die eingegebene Zahl maximal sein?

Dieser Rechner unterstützt Zahlen bis 1.000.000.000.000 (10¹², eine Billion). Er verwendet die Probedivision bis √n, was maximal etwa eine Million Schritte erfordert und im Browser schnell genug läuft. Für größere Zahlen werden spezielle Algorithmen wie das Pollard-Rho-Verfahren oder das quadratische Sieb eingesetzt.