Größten gemeinsamen Teiler rausfinden

Stromberg

Ich möchte den größten gemeinsamen Teiler rausfinden, und wollte das mit dem Euklidischen Algorithmus machen, aber irgendwie blick ich da net so durch, bin wohl kein großese Mathe Genie (auch nicht in der Schule )!
Ja also ich würde das jetzt so machen aber es geht nicht (kommt nä ganz komische Zahl raus):

int ggt(int a,int b)
{
    if (a>b)
    {
        a=a-b;
        if (a>b)
        {
            ggt(a,b);
        }
        if (a<b)
        {
            ggt(b,a);
        }
    }
    if (b>a)
    {
        b=b-a;
        if (b>a)
        {
            ggt(b,a);
        }
        if (b<a)
        {
            ggt(a,b);
        }
    }
    if (a==b)
    {
        return a;
    }
}

Aber so ging das doch (habs ich zumindestens in Erinnerung), oder nicht?
Kann mir jemand helfen? Dankeschön schon mal im Voraus.

Konrad Rudolph

Wow, wie aufwendig.

int ggt(int a, int b)
{
    if (b == 0) return a;
    else        return ggt(b, a % b);
}

Shinja

Fehlt ne Kleinigkeit, oder?

if(a<b){int c=a;a=b;b=c;}

vor dem if(b==0)

Oder ueberseh ich da was?

EDIT: und wenn ich das richtig sehe meint der Threadersteller den Algorithmus durch Substrahieren, oder?

EDIT 2: ich HAB was uebersehen. War ja klar. Wird ja automatisch geswitched wenns nicht passt...

EDIT 3: ich glaube der "gedachte" Weg war:

int ggt(int a,int b){
    if(a==b) return a;
    if(a>b) return ggt(b,a-b);
    return ggt(b-a,a);
}

Ist natuerlich nicht so performant wie die andere variante (und funktionniert nur fuer positive Zahlen) Aber da der Threadersteller nur - und kein % benutzt hat koennte er vielleicht diesen Algorithmus gemeint haben. Ich hoffe ich habe mich jetzt richtig erinnert, habe den nur einmal als Programmieruebung kurz schreiben muessen, aber eigentlich nie angewandt. Falls inkorrekt bitte berichtigen.

SG1

Nein, fehlt nicht. Wenn a und b falschrum sind, wird das beim ersten rekursiven Aufruf korrigiert.