Primfaktorisierungsbaum

Bei der Primfaktorzerlegung wird eine ganze Zahl in die Primzahlen zerlegt, die durch Multiplikation zu dieser Zahl führen – die einzige Zerlegung, die jede zusammengesetzte Zahl hat, und zwar genau eine. Dieses Tool nimmt eine beliebige Ganzzahl von 2 oder mehr und faktorisiert sie reell. Anschließend stellt es das Ergebnis als den in der Schule gelehrten Verzweigungsfaktorbaum dar: Beginnen Sie mit der Zahl, teilen Sie den kleinsten Primfaktor ab und teilen Sie das verbleibende Teil so lange auf, bis nur noch Primzahlen übrig sind.

Die Teilungsregel ist eine Probedivision durch die kleinstmögliche Primzahl bei jedem Schritt: Probieren Sie zuerst 2, dann die ungeraden Zahlen 3, 5, 7, 9 ... bis zur Quadratwurzel des aktuellen Wertes. Für 360 lautet das: 360 = 2 × 180, dann 180 = 2 × 90, dann 90 = 2 × 45, dann 45 = 5 × 9, dann 9 = 3 × 3 – fünf Teilungen, die in sechs Hauptblättern enden (2, 2, 2, 3, 3, 5). Das Zählen dieser Blätter ergibt die unter dem Diagramm gezeigte kompakte Exponentenform: 360 = 2³ × 3² × 5.

All dies läuft mit exakter BigInt-Arithmetik ab, so dass es auf dem Weg nach unten nie zu einer Gleitkomma-Rundung kommt. Die Probedivision bis zur Quadratwurzel geht bei alltäglichen Zahlen schnell, wird aber umso langsamer, je größer der kleinste Primfaktor der Eingabe ist. Daher begrenzt das Tool die Eingabe auf 1.000.000.000.000 (10^12) und meldet darüber hinaus eine ehrliche Nachricht, anstatt die Registerkarte einzufrieren – ein Browser hat nichts damit zu tun, an einer riesigen Halbzahl festzuhalten, nur um einen Punkt zu beweisen.

Ein visueller Faktorbaum ist die Standardmethode, mit der die Primfaktorzerlegung in der Schule gelehrt wird, und er bleibt weit über das Klassenzimmer hinaus nützlich: Brüche zu reduzieren, den größten gemeinsamen Faktor oder das kleinste gemeinsame Vielfache durch Vergleich von Primzahlpotenzen zu finden, Quadratwurzeln zu vereinfachen und stichprobenartig zu prüfen, ob eine Zahl eine Primzahl ist, kommt alle auf die gleiche Zerlegung zurück. Alles läuft lokal in Ihrem Browser – keine Anmeldung, kein Server-Roundtrip.