Primfaktorzerlegung - Gibt es einen Trick?

Question

Wenn ich hohe zahlen wie zB 372 habe, wie komme ich dann auf die zugehörigen primzahlen? Also welches primzahlen multipliziert auf 372 kommen?

Ist das nur ausprobieren oder gibt es einen bestimmten rechenweg?

Answer 1

372 = 2 * 186
372 = 2 * 2 * 93
372 = 2 * 2 * 3 * 31

Fertig!

Comments

Ja, das prinzip ansich ist mir klar. Aber ich komme da nur durch ausprobieren hin. gibt es irgendnen trick den man anwenden kann ohne dass man einfach nur ausprobiert, was ja manchmal sehr lang dauern kann.


Genauso, wenn die frage gestellt ist, welche positiven teiler 372 hat. Ich komme da nur durch ausprobieren hin und wie gesagt, das dauert bei mir immer. Gibt es nicht irgendnen rechenweg/trick wie auch immer der einem zeit erspart?

---

Bequem ist es nicht:
Solange durch 2 teilen, bis es nicht mehr geht,
dann durch 3 teilen, bis es nicht mehr geht,
dann durch 5

durch 7

durch 11

etc. die Primzahlen hoch.

---

Du teilst ja immer wieder durch eine Primzahl. Dazu ist es günstig die Primzahlen bis 100 zu kennen.

Günstig ist wenn du weißt das neben den ersten Primzahlen 2 und 3 die weiteren Primzahlen auf den Stellen 6n-1 und 6n+1 liegen können.

6 also 5 und 7

12 also 11 und 13

18 also 17 und 19

24 also 23 und 25. das 25 hier nicht prim ist weiß man aber sodass ich die nicht testen muss.

Ich brauche allerdings immer nur bis zur Wurzel des übrigen Faktors probieren.

---

Also nehmen wir mal 12345

Das es durch 5 geht sehe ich sofort

12345 : 5 = 2469

Das das durch 3 geht sehe ich auch sofort weil die Quersumme auch durch 3 teilbar ist.

2469 : 3 = 823

jetzt muss ich ungünstigerweise alle Weiteren Primzahlen bis √823 = 28 testen. Dazu gehören wie oben gesagt

7, 11,13,17,19 und 23. Die 29 brauch ich nicht mehr testen, da diese über 28 liegt.

Da die 823 durch keine dieser 6 Zahlen teilbar ist ist 823 prim.