✔ GGT Effizienz

[Java/CppProgrammer]

Hallo allerseits.
Ich hoffe meine Frage ist hier richtig:

Der Größte Gemeinsame Teiler (GGT) zweier Zahlen ist ja bekanntlich die größte Zahl, durch die sich beide ohne Rest Teilen lassen.
Um den GGT Teiler zweier Zahlen bestimmen zu lassen, hab ich folgende Funktion geschrieben (ich wähl jetzt einfach C++, weil das wohl für die meisten lesbar sein wird):

int ggt(int Zahl1,int Zahl2)
{
int x=1;
for (int i = 1; i <= ((Zahl1 < Zahl2) ? Zahl1 : Zahl2); i++)
{
if ((Zahl1 % i == 0) && (Zahl2 % i == 0))
x=i;
}
return x;
}

Es wird in der Schleife jeder ganzzahlige Wert größer Null daraif überprüft, ob er durch die beiden Zahlen ohne Rest teilbar ist.

Meine Frage ist, ob es nicht auch effizientere Wege gibt (ähnlich wie bei den isPrimzahl Funktionen, die Seitenlange Code haben), denn die Funktion hier dauert bei größeren Zahl en schon etwas.

Danke

 

[Tobias Menzel]

Hi,

normalerweise macht man das rekursiv mit der Modulo-Funktion:

public int ggT(int a, int b) {
   if (a == b || b == 0 ) return a;
   return ggT(b, a % b);
}

Gruß
.

 

[Thomas Darimont]

Hallo!

Normalerwerise macht man das so:

/*
 * Created on 05.02.2005@14:00:13
 *
 * TODO Licence info
 */
package de.tutorials;

/**
 * @author Administrator
 *
 * TODO Explain me
 */
public class GCDTest {

    public static void main(String[] args) {
        System.out.println(gcd(21, 21));
    }

    /**
     * @param i
     * @param j
     */
    private static int gcd(int i, int j) {
        if (j == 0)
            return i;
        else
            return gcd(j, i % j);
    }
}

Mit Datics "Optimierung" if (a == b || b == 0 ) spart man sich im Fall a == b einen rekusiven Aufruf.

Gruß Tom

 

[Java/CppProgrammer]

Okay, vielen Dank.