kgV berechnen ohne Primfaktorzerlegung
Hallo wie berechnet man den kgv von zwei zahlen ohne die Primfaktorzerlegung und ohne dass man die Vielfache aufschreibt. Gibt es eine feste formel dafür?
3 Antworten
Siehe Hypergerd, die dividierst das Produkt u v der Zahlen u und v durch deren größten gemeinsamen Teiler (ggT), um kgV(u,v) zu erhalten.
Denn ggT wiederum findest du (ohne Primfaktorzerlegung) mit Euklidischer Division. Diese ist in >http://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus erklärt.
die vielfachen der größeren Zahl berechnen und anschließend die Vielfachen der kleineren Zahl. Die erste Zahl, die dann doppelt erscheint, ist dasd kgV
Ein möglicher Algorithmus besteht aus 2 Funktionen:
Kurzform:
Funktion kgV(a,b) = a * b / ggT(a,b)
und
Funktion ggT(a,b)
untersucht Divisionsreste, solange bis kein Rest mehr ...
etwas genauer siehe http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php
3. Kombobox-Eintrag
kann man auch online 64 stellige Zahlen ausrechnen