Supportnet / Forum / Anwendungen(Java,C++...)
GGT und KGV
Frage
Hallo zusammen,
kennt jemand eine analytische Formel bzw. einen schnellen Algorithmus zur Berechnung von GGT und KGV? Die Sprache ist eigentlich egal..
Gruß
Bernd B.
Antwort 1 von semi
Ist C OK?
int ggt(int a, int b)
{
int c;
do
{
c=a % b;
a=b; b=c;
}
while(b!=0);
return a;
}
// Alternative Lösung
int ggt2(int a, int b)
{
while (a <> b)
{
if (b > a)
b -= a;
else
a -= b;
}
return a;
}
int kgv(int a, int b)
{
return a*b/ggt(a,b);
}Antwort 2 von Bernd das Brot
Thanx! Ist ja echt nicht so kompilziert. Aber für'n Brot....
Einen nicht iterativen Ansatz gibt's wohl nicht, oder?
Bernd
Einen nicht iterativen Ansatz gibt's wohl nicht, oder?
Bernd
Antwort 3 von semi
> Einen nicht iterativen Ansatz gibt's wohl nicht, oder?
Ist mir noch keiner untergekommen :)
Das ist aber schnell genug.
z.B. in Java
- Zeit ca. 469ms auf meinem AMD 2400+
- Die int-casts und random() Aufrufe nicht abgezogen
Ist wirklich die falsche Stelle für Optimierungen :)
Gruß,
Michael
Ist mir noch keiner untergekommen :)
Das ist aber schnell genug.
z.B. in Java
long startTime = System.currentTimeMillis();
for(int i=0; i<1000000; i++)
ggt(
(int)(Math.random()*10000)+1,
(int)(Math.random()*10000)+1
);
System.out.println(
(System.currentTimeMillis()-startTime)+"ms"
);- Zeit ca. 469ms auf meinem AMD 2400+
- Die int-casts und random() Aufrufe nicht abgezogen
Ist wirklich die falsche Stelle für Optimierungen :)
Gruß,
Michael