Primfaktorzerlegung

• Zerlegung einer natürlichen Zahl in ein Produkt aus Primzahlen

Kurzanleitung:

• Die vorliegende Zahl so lange in ein Produkt aus anderen Zahlen aufbrechen, bis es sich bei den Faktoren ausschließlich um Primzahlen handelt.
• Wenn man sich unsicher ist, ob es sich bei einem der Faktoren um eine Primzahl handelt: Primzahl-Test

Beispiel: Primfaktorzerlegung von 1000:

Formalisiertes Vorgehen

1. Liste mit den ersten Primzahlen parat legen
2. Zahl festlegen, deren Primfaktorzerlegung bestimmt werden soll (erste Ausgangszahl)
3. Versuchen, die Ausgangszahl durch die erste Primzahl (2) zu teilen
   • Falls möglich: Weiter zu Schritt 4
   • Falls nicht möglich: Versuch mit der nächst höheren Primzahl wiederholen, bis:
     • entweder der Versuch aufgeht → Schritt 4
     • die Ausgangszahl selbst als Primzahl erkannt wird → Schritt 5
     • das Quadrat der aktuellen Primzahl größer ist als die Ausgangszahl → Schritt 5
4. Aktuelle Primzahl als Primfaktor notieren
   • Ergebnis der Division = neue Ausgangszahl
   • Schritt 3 wiederholen
5. Die aktuelle Ausgangszahl ist der letzte Primfaktor
   • Die Primfaktorzerlegung ergibt sich als Liste aller bisher notierten Primzahlen
   • Falls bisher keine Primzahlen notiert wurden, handelt es sich bei der ersten Ausgangszahl um eine Primzahl, welche keine Primfaktoren besitzt

Beispiel