Rechner zur Primfaktorzerlegung

Die Primfaktorzerlegung stellt eine positive ganze Zahl als Produkt von Primzahlen dar. Eine Primzahl hat genau zwei positive Teiler, eins und sich selbst. Primzahlen bilden daher die unteilbaren Bausteine der Multiplikation ganzer Zahlen. Beispielsweise lässt sich 360 als 2 × 2 × 2 × 3 × 3 × 5 oder kompakter als 2³ × 3² × 5 schreiben. Der Fundamentalsatz der Arithmetik garantiert, dass jede ganze Zahl größer als eins bis auf die Reihenfolge der Faktoren genau eine Primfaktorzerlegung besitzt. Der Rechner verwendet Probedivision. Zuerst entfernt er sämtliche Faktoren zwei und zählt, wie oft die Division aufgeht. Anschließend prüft er ungerade mögliche Teiler in aufsteigender Reihenfolge. Die Prüfung endet, sobald das Quadrat des Kandidaten die verbleibende Zahl übersteigt. Ein zusammengesetzter Rest hätte nämlich einen Faktor kleiner oder gleich seiner Quadratwurzel. Bleibt ein Rest größer als eins übrig, ist dieser eine Primzahl und wird zum letzten Faktor. Exponenten machen wiederholte Faktoren übersichtlich. Bei 2³ bedeutet der Exponent drei, dass drei Zweien miteinander multipliziert werden. Eine nur einmal vorkommende Primzahl wird ohne Exponenten angezeigt. Die Zahl verschiedener Faktoren gibt an, wie viele unterschiedliche Primzahlen vorkommen, nicht wie viele Primfaktoren einschließlich Wiederholungen vorhanden sind. So hat 360 drei verschiedene Primfaktoren, mit Vielfachheiten jedoch sechs. Die Primfaktorzerlegung hilft beim Kürzen von Brüchen, Bestimmen größter gemeinsamer Teiler und kleinster gemeinsamer Vielfacher, Erkennen vollständiger Quadrate oder Kuben und Lösen von Teilbarkeitsaufgaben. Für den größten gemeinsamen Teiler vergleichst du die Zerlegungen und verwendest jede gemeinsame Primzahl mit dem kleineren Exponenten. Für das kleinste gemeinsame Vielfache nimmst du alle vorkommenden Primzahlen mit ihrem jeweils größeren Exponenten. Eine Zahl ist genau dann eine Quadratzahl, wenn alle Exponenten ihrer Primfaktorzerlegung gerade sind. Auch die Kryptografie nutzt den Unterschied zwischen Multiplikation und Faktorisierung. Zwei große Primzahlen zu multiplizieren ist einfach; sie aus ihrem Produkt zurückzugewinnen kann dagegen rechnerisch schwierig sein. Dieser Browserrechner ist für übliche Zahlen in Unterricht und Praxis gedacht, nicht für Angriffe auf Zahlen in kryptografischer Schlüsselgröße. Sehr große Primzahleingaben können viele Probedivisionen erfordern, obwohl offensichtliche kleine Faktoren schnell entfernt werden. Der Wertebereich beginnt bei zwei, weil eins weder prim noch zusammengesetzt ist und einem leeren Primzahlprodukt entspricht. Null und negative ganze Zahlen benötigen zusätzliche Konventionen: Null hat keine Primfaktorzerlegung, während eine negative ganze Zahl als -1 mal die Zerlegung ihres Betrags dargestellt werden kann. Gib hier eine positive ganze Zahl ein, um die übliche eindeutige Form aus Arithmetik und Zahlentheorie zu erhalten.