Primfaktorenzerlegung

Bei der Primfaktorzerlegung geht es darum, eine ganze Zahl als Produkt von Primzahlen darzustellen. Dazu prüft man, ob sich die Zahl durch eine Primzahl teilen läßt. Man begint mit der kleinsten Primzahl, der 2. Wenn die Zahl teilbar ist, führt man die Division aus, und erhält ein Zwischenergebnis. Man prüft, ob sich das Zwischenergebnis noch mal durch die gleiche Primzahl teilen läßt. Wenn ja, führt man die Division erneut aus und erhält ein neues Zwischenregebnis, wenn nicht, dann nimmt man die nächst größere Primzahl. Der Algorithmus ist beendet, wenn das Zwischenergebnis eine Primzahl ist. Das letzte Zwischenergebnis ist der letzte Faktor der Primzahlenzerlegung.

Als Beispiel zerlegen wir die Zahl 12 in Primfaktoren. 12 kann man durch 2 teilen und erhält das Zwischenergebnis 6. Die Zahl 6 kann man noch mal durch 2 teilen und man erhält das Zwischenergebnis 3. Das Zwischenergebnis 3 ist eine Primzahl, damit ist der Algorithmus beendet. Die Primfaktoren von 12 sind 2,2,3 oder auch 12=2∙2∙3.