C Suche Algorithmus zum Bestimmen vom kgV MEHRERER Werte

Also den Algorithmus für den ggT mehrerer Werte habe ich nun nach einigem Kopfzerbrechen hinbekommen:

http://pastebin.com/B4CQxVwS

Wenn ich nun von genau den gleichen Werten den kgV bestimmen möchte, kann ich dann nicht irgendwie diesen Zusammenhang hier nutzen ?

http://de.wikipedia.org/wiki/Kleinstes_gemeinsames_Vielfaches#Zusammenhang_von_kgV_und_ggT

Daraus folgt ja:

kgV (m, n) = (m*n) / ggT (m, n)

Nur das Problem ist ja, dass ich nicht nur zwei Werte m und n habe, sondern beliebig viele.
Aber trotzdem könnte ich ja vielleicht daraus einen Algorithmus erstellen, hat jemand eine Idee ?

Oder evtl. einen Algorithmus der allgemein von mehreren Zahlen den kgV bestimmt ?

Das hier gilt zwar "nur" für drei Werte, aber ich denke, analog zu deiner Lösung für den ggT kannst du hier auch vorgehen:

ggT(a,b,c)*kgV(ab,ac,bc) = |abc|

Quelle

Hallo,

Wie effizient muss das Programm denn sein?

Eine Moeglichkeit waere, die Primzahlzerlegung einer jeden Zahl zu bestimmen und dann einfach das Produkt der hoechsten Primzahlpotenzen zu berechnen.
Das geht mit jeder beliebigen Anzahl an Zahlen; hat nur leider den Nachteil, dass man einen Algorithmus braucht, der Primzahlen bestimmt. Der Rest ist dann Programmier-Ein-mal-Eins.

Gruss

Wende deine Formel doch iterativ an. kgV der ersten beiden Zahlen berechnen und dieses Teilergebnis dann mit einer weiteren wieder in deine Formel einsetzen usw.

Effizienz des Programms ist ziemlich egal.

nullPtr schrieb:

Wende deine Formel doch iterativ an. kgV der ersten beiden Zahlen berechnen und dieses Teilergebnis dann mit einer weiteren wieder in deine Formel einsetzen usw.

Zum Vergrößern anklicken....

Das klingt nach einer simplen Lösung, verstehe nur noch nicht ganz wie der Zusammenhang von den kgV's ist.

Sagen wir mal einfaches Beispiel, wir haben die drei Werte 2, 4 und 6 (das kgV wäre ja 12)

Für die ersten beiden Zahlen gilt ja:

kgV(2, 4) = (2 * 4) / ggT (2, 4)

ich nenne das orangene einfach mal X

Aber in welchem Zusammenhang steht nun der kgV von den ersten beiden Zahlen mit der dritten Zahl ?

Gilt dieser Zusammenhang hier ?

kgV(2, 4, 6) = kgV(X, 6) = (X * 6 / ggT (X, 6)

Ja, der Zusammenhang gilt.

kgV(a,b,c) = kgV(a,kgV(b,c))

(wie auch bereits in allgemeiner Form in meiner oben geposteten Quelle steht)