[Swift] ggT und kgV berechnen

[AppDev04]

Hallo
Für meine App ist es wichtig, dass ich den ggt (größter gemeinsamer Teiler) und kgV (kleinste gemeinsame Vielfache) von verschiedenen Zahlen berechnen kann. Ich habe es jetzt lange versucht etwas zu coden, komme aber nie auf die richtigen Lösungen. Kann mir jemand einen Ansatz geben, wie ich das angehen kann?

 

[KALLT]

Wie viele Zahlen willst du denn vergleichen? Wie sah denn deine Lösung aus? Vielleicht ist hilfreich um dir dabei auf die Sprünge zu helfen, statt direkt eine Lösung zu präsentieren.

 

[AppDev04]

Es soll einmal mit 2 Zahlen und einmal mit 3 Zahlen verglichen werden. Um ehrlich zu sein, abe ich noch keinen richtigen Ansatzpunkt. Ich denke es muss etwas sein mit einem Loop der überprüft, ob die Zahl teilbar ist und noch eine ganze Zahl ergibt

 

[ToRa]

ob die Zahl teilbar ist und noch eine ganze Zahl ergibt

Ganz so einfach ist die Thematik aus meiner Sicht nicht. Schon mal was von Primfaktorzerlegung gehört? Über die bekommst du den ggT bzw. kgV.

 

[AppDev04]

Ich habe hier ein gutes Tutorial gefunden, für all jene die sich dafür interessieren:
https://github.com/raywenderlich/swift-algorithm-club/tree/master/GCD

 

[double_d]

Die schnellste Methode beim ggT und zwei Zahlen dürfte wohl der euklidische Algorithmus sein.
Den verwenden auch die meisten Scripts im Internet, die ich kenne.
Ansonsten ggT >2 Zahlen und kgV wirst Du um die Primfaktorzerlegung nicht umhin kommen.

 

[KALLT]

Diese Lösung wird auch im Link beschrieben. Quasi Modulo (A % B) in Kombination mit einer Rekursion bis zur 0. Allerdings sind damit natürlich immer nur zwei Zahlen gleichzeitig möglich.