(Mathematik) die gemeinsamen Teiler zweier Zahlen bestimmen?
Hallo, Bei diesem Beitrag wollte ich die Frage stellen wie ich die gemeinsamen Teiler zweier Zahlen schnell berechnen kann ( nicht den Ggt) Danke schon im Voraus
2 Antworten
Der GGT ist schon die Basis.... mit dem euklidischen Algorithmus zu ermitteln.
Wenn du den hast, sind alle Teiler davon gemeinsame Teiler der beiden Zahlen.
Das ist vermutlich effizienter, als (wie auch vorgeschlagen) beide Zahlen in Primfaktoren zu zerlegen (was seht schwierig sein kann). Wenn GGT = 1 bist du so jedenfalls i.d.R. schneller fertig.
Durch Primfaktorzerlegung kannst du alle gemeinsamen Primfaktoren bestimmen, deren multiplikative Kombination die gemeinsamen Teiler bilden.
Ein schnelles Verfahren habe ich da nicht zur Hand. Ich würde anfangen mit den einstelligen Primzahlen und deren Teilbarkeitsregeln.