Primfaktorzerlegung | Gemeinsame Teiler | Gemeinsame Vielfache | Teiler | Radikal

Primfaktorzerlegung

Von einer ganzen Zahl werden die Primfaktoren errechnet und ausgegeben (Faktorisierung). Die Primfaktoren sind jene Primzahlen, durch die eine gegebene Zahl teilbar ist. Primzahlen sind nur durch Eins und durch sich selber ohne Rest teilbar. Geben Sie eine Zahl mit maximal 13 Stellen (Billionen) ein und klicken Sie auf Berechnen. Die Berechnung hoher Zahlen (über 7 Stellen) kann eine Weile dauern.

Die Kenntnis der Primfaktoren von Zahlen erleichtert das Dividieren zweier Zahlen und das Auffinden von größtem gemeinsamen Teiler (ggT) und kleinstem gemeinsamen Vielfachen (kgV). In einer häufig benutzten Metapher werden Primzahlen als die Atome der Mathematik bezeichnet. Aus der Multiplikation von Primzahlen lassen sich alle natürlichen Zahlen bilden, welche dann nach diesem Bild die Moleküle darstellen. Primzahlen und Primfaktoren spielen eine Hauptrolle in der Zahlentheorie, welche sich mit der Eigenschaft von Zahlen beschäftigt.

Die Primfaktorzerlegung ist eine Faktorisierung, es gibt in der Mathematik auch noch andere Faktorisierungen, beispielsweise von Polynomen. Bei dem simpelste Algorithmus zur Faktorisierung von natürlichen Zahlen wird mit der 2 begonnen. Wenn die gewählte Zahl durch 2 teilbar ist, dann ist 2 ein Primfaktor, es wird durch 2 geteilt und mit der gleichen Zahl weiter gemacht, bis der verbleibende Wert nicht mehr durch 2 teilbar ist. Dann macht man genau so mit 3 weiter und so weiter mit den folgenden Primzahlen (oder den folgenden natürlichen Zahlen, keine Primzahlen liefern einfach keine Ergebnisse). Sobald der verbleibende Wert 1 ist, wird aufgehört. Für sehr große Zahlen ist diese Methode extrem rechenaufwändig. Es gibt zwar noch weitere Verfahren, davon ist aber keines effizient. Das macht die Faktorisierung von sehr großen Zahlen so schwierig, weswegen diese in der Kryptografie Verwendung finden.