Primfaktorzerlegungsrechner

So Funktioniert Dieser Rechner

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:

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