Primfaktorzerlegung - Wie geht das?

Das einfachste Verfahren zur Zerlegung einer Zahl in seine Primfaktoren ist die sogenannte Probedivision. Bei diesem Verfahren wird probiert, daher der Name, ob sich die Zahl, die zerlegt werden soll, durch Primzahlen teilen lässt oder nicht.

Das Verfahren funktioniert dabei wie folgt. Angenommen die Zahl Z soll in ihre Primfaktoren zerlegt werden. Als Erstes wird die Quadratzahl Q gesucht, die größer gleich (≥) der Zahl Z ist, also Q ≥ Z. Als Nächstes zieht man die Wurzel aus √Q = W . Damit kann bestimmt werden, welche Primzahlen man ausprobieren muss, um die Zahl Z in ihre Primfaktoren zu zerlegen. Es sind alle Primzahlen, die zwischen der 2 und der Zahl W liegen. Zu Beginn wird die Zahl Z so lange durch 2 geteilt, bis dies nicht mehr möglich ist. Anschließend wird Z durch 3 geteilt, bis auch das nicht mehr möglich ist. Dann folgen die 5, die 7 usw., bis man die Zahl W erreicht hat. Dann hat man entweder die Primfaktorzerlegung der Zahl Z oder für den Fall, dass die Zahl von keiner der Primzahlen geteilt wurde, gezeigt, das Z selbst auch eine Primzahl ist.

Das ganze Verfahren lässt sich, wenn man die Teilbarkeitsregeln kennt, beschleunigen, da einem dann die Fälle erspart bleiben in denen am Ende der Division ein Rest vorhanden bleibt.

Beispiele

Gesucht ist die Primfaktorzerlegung von 126.
  1. Die nächst größere Quadratzahl ist 144.
  2. Die Wurzel aus 144 ist 12.
  3. Primzahlen die mögliche Teiler sind, sind 2,3,5,7 und die 11.
    1. 126 ist durch 2 teilbar und 126 : 2 = 63
    2. 63 ist nicht durch 2 teilbar.
    3. 63 ist durch 3 teilbar und 63 : 3 = 21
    4. 21 ist durch 3 teilbar und 21 : 3 = 7
    5. 7 ist eine Primzahl.
  4. Die Primfaktoren von 126 sind 2,3,3,7. Und 126 = 2 · 3 · 3 · 7 = 2 · 32 · 7.
Gesucht ist die Primfaktorzerlegung von 127.
  1. Die nächst größere Quadratzahl ist 144.
  2. Die Wurzel aus 144 ist 12.
  3. Primzahlen die mögliche Teiler sind, sind 2,3,5,7 und die 11.
    1. 127 ist nicht durch 2 teilbar.
    2. 127 ist nicht durch 3 teilbar.
    3. 127 ist nicht durch 5 teilbar.
    4. 127 ist nicht durch 7 teilbar.
    5. 127 ist auch nicht durch 11 teilbar.
  4. 127 ist selbst eine Primzahl. Daher ist die Primfaktorzerlegung 127.

Nachteile

Für kleinere Zahlen eignet sich das Verfahren ganz gut, aber spätestens wenn die untersuchten Zahlen sehr groß werden ergeben sich die zwei folgenden Probleme. Das erste Problem ist das Finden der passenden Quadratzahl. Das Problem lässt sich aber dadurch lösen, das man die Wurzel aus der Zahl Z zieht und einfach auf die nächste ganze Zahl aufrundet. Das zweite Problem ist, dass man alle Primzahl zwischen 2 und der Wurzel aus Z bereits kennen muss. Hier kann man im Zweifel auf Listen mit Primzahlen zurückgreifen.

Beispiel

Gesucht ist die Primfaktorzerlegung von 75600.
  1. Die nächst größere Quadratzahl ist 75625.
  2. Die Wurzel aus 75625 ist 275.
  3. Mögliche Teiler sind alle Primzahlen zwischen 2 und 271 und das sind über 50 Stück!
    1. 75600 ist durch 2 teilbar und 75600 : 2 = 37800
    2. 37800 ist durch 2 teilbar und 37800 : 2 = 18900
    3. 18900 ist durch 2 teilbar und 18900 : 2 = 9450
    4. 9450 ist durch 2 teilbar und 9450 : 2 = 4725
    5. 4725 ist nicht durch 2 teilbar.
    6. 4725 ist durch 3 teilbar und 4725 : 3 = 1575
    7. 1575 ist durch 3 teilbar und 1575 : 3 = 525
    8. 525 ist durch 3 teilbar und 525 : 3 = 175
    9. 175 ist nicht durch 3 teilbar
    10. 175 ist durch 5 teilbar und 175 : 5 = 35
    11. 35 ist durch 5 teilbar und 35 : 5 = 7
    12. Und 7 ist eine Primzahl.
  4. Die Primfaktoren von 75600 sind 2,2,2,3,3,3,5,5,7. Und 75600 = 2 · 2 · 2 · 2 · 2 · 3 · 3 · 3 · 5 · 5 · 7 = 24 · 33 · 52 · 7.

Verbesserungen

Wenn man große Zahlen, ohne die oben beschrieben Lösungen, zerlegen will, kann auch die Reihenfolge des Verfahrens geändert werden. Dies funktioniert dann, wenn man bereits einen der Primteiler dieser Zahl kennt. Angenommen die Zahl endet auf 2,4,6 oder 8 dann ist die Zahl 2 ein Teiler dieser Zahl. Die Zahl wird dann so lange durch die 2 geteilt, bis dies nicht mehr möglich ist. Ähnliche Teilbarkeitsregeln gibt es auch für 4,8,16 usw., wodurch sich dieser Vorgang deutlich beschleunigt. Oder wenn die Zahl auf 0 endet, ist sie durch 10 teilbar, bei der Endung auf 00 durch 100 usw. Wenn die Zahl ungerade ist, können die 3, 5 und Vielfache der Fünf, oder 7 als Teiler probiert werden. Auf die so verkleinerte Zahl kann wieder das ursprüngliche Verfahren angewendet werden, um die restlichen Faktoren zu bestimmen.

Beispiel

Gesucht ist die Primfaktorzerlegung von 75600.
  1. 75600 ist durch 100 teilbar und 75600 : 100 = 756
  1. Die nächst größere Quadratzahl ist 784
  2. Die Wurzel aus 784 ist 28.
  3. Mögliche Teiler sind alle Primzahlen zwischen 2 und 23 und das sind nur 9 Stück!
  4. 756 ist durch 2 teilbar und 756 : 2 = 378
  5. 378 ist durch 2 teilbar und 378 : 2 = 189
  6. 189 ist nicht durch 2 teilbar.
  7. 189 ist durch 3 teilbar und 189 : 3 = 63
  8. 63 ist durch 3 teilbar und 63 : 3 = 21
  9. 21 ist durch 3 teilbar und 21 : 3 = 7
  10. Und 7 ist eine Primzahl.
  11. Die Primfaktoren von 756 sind 2,2,3,3,3,7. Und 756 = 2 · 2 · 3 · 3 · 3 · 7 = 22 · 33 · 7.
  • Jetzt müssen die Primfaktoren für 100 bestimmt werden.
    1. Die nächst größere bzw. gleiche Quadratzahl ist 100
    2. Die Wurzel aus 100 ist 10.
    3. Primzahlen die mögliche Teiler sind, sind 2,3,5,7.
    4. 100 ist durch 2 teilbar und 100 : 2 = 50
    5. 50 ist durch 2 teilbar und 50 : 2 = 25
    6. 25 ist nicht durch 3 teilbar
    7. 25 ist durch 5 teilbar und 25 : 5 = 5
    8. Und 5 ist eine Primzahl.
    9. Die Primfaktoren von 100 sind 2,2,5,5. Und 100 = 2 · 2 · 5 · 5 = 22 · 52.
    10. Die Primfaktoren von 75600 sind 2,2,3,3,3,7 und 2,2,5,5. Und 75600 = 2 · 2 · 2 · 2 · 2 · 3 · 3 · 3 · 5 · 5 · 7 = 24 · 33 · 52 · 7.

    Anwendungsgebiete

    Die Primfaktorzerlegung kann dazu genutzt werden um …