Primfaktorzerlegung-Rechner

Was ist ein Primfaktorzerlegung-Rechner?

Ein Primfaktorzerlegung-Rechner nimmt eine ganze Zahl und schreibt sie als Produkt von Primzahlen um. Eine Primzahl ist eine ganze Zahl größer als 1, deren einzige Teiler 1 und sie selbst sind, etwa 2, 3, 5, 7 und 11. Jede ganze Zahl größer als 1 ist entweder prim oder kann als eindeutiges Produkt von Primzahlen geschrieben werden — ein Ergebnis, das als Fundamentalsatz der Arithmetik bekannt ist. Dieser Rechner führt diese Zerlegung für Sie durch und zeigt die Faktoren als Ziffern, die durch das Multiplikationszeichen verbunden sind, zum Beispiel $60 = 2 \times 2 \times 3 \times 5$.

Da die Ausgabe nur aus Ziffern und dem Multiplikationssymbol besteht, liest sie sich in jeder Sprache gleich.

Wie funktioniert er?

Der Rechner verwendet die Probedivision, die direkteste Faktorisierungsmethode. Ausgehend von der kleinsten Primzahl teilt er die Zahl wiederholt durch jeden möglichen Teiler, solange die Division aufgeht, und geht dann zum nächsten Kandidaten über:

1. Setze einen Teiler $d = 2$.
2. Solange die Zahl durch $d$ teilbar ist, notiere $d$ als Faktor und teile die Zahl durch $d$.
3. Erhöhe $d$ und wiederhole. Du musst nur Teiler bis zur Quadratwurzel der Zahl testen, denn wenn $d \times d$ den Rest übersteigt, ist der verbleibende Wert selbst prim.
4. Wenn am Ende etwas Größeres als 1 übrig bleibt, ist auch dies ein Primfaktor.

In Formelschreibweise ist das Ergebnis das Produkt

$n = p_1 \times p_2 \times \cdots \times p_k$

wobei jedes $p_i$ prim ist und die Primzahlen von der kleinsten zur größten aufgelistet werden, mit explizit angegebenen Wiederholungen.

Durchgerechnete Beispiele

• 12 ist durch 2 teilbar und ergibt 6, dann erneut durch 2 und ergibt 3, was prim ist. Also $12 = 2 \times 2 \times 3$.
• 60 ist durch 2 teilbar und ergibt 30, erneut durch 2 und ergibt 15, dann durch 3 und ergibt 5, was prim ist. Also $60 = 2 \times 2 \times 3 \times 5$.
• 17 hat keinen Teiler bis zu seiner Quadratwurzel (etwa 4,12), ist also prim, und die Zerlegung ist einfach $17$.
• 100 ist zweimal durch 2 teilbar und ergibt 25, dann zweimal durch 5 und ergibt 1. Also $100 = 2 \times 2 \times 5 \times 5$.

Praktische Hinweise

• Die kleinste Eingabe ist 2, da 0, 1 und negative Zahlen keine Primfaktorzerlegung haben. Die Eingabe von 1 oder ein leeres Feld liefert ein leeres Ergebnis.
• Wiederholte Faktoren werden einzeln aufgelistet und nicht als Potenzen, sodass 100 als $2 \times 2 \times 5 \times 5$ statt als $2^2 \times 5^2$ erscheint.
• Die Primfaktorzerlegung ist die Grundlage zum Bestimmen des größten gemeinsamen Teilers und des kleinsten gemeinsamen Vielfachen zweier Zahlen: Nimm die Primzahlen, die sie gemeinsam haben, für den GGT, und kombiniere alle Primzahlen für das KGV. Um jeden Teiler einer Zahl zu sehen und nicht nur ihre Primzahlen, verwende den Faktor-Rechner.