Inom matematiken är den största gemensamma delaren av två heltal det största heltal som delar båda talen. Den förkortas SGD. Ett av talen kan vara noll, men inte båda.
Exempel:
SGD(30,12) är 6 eftersom både 30 och 12 är delbara med 6 och det finns inga heltal större än 6 som delar både 30 och 12.
SGD(85,17) är 17 eftersom 85 är delbart med 17 (85=17*5) och självklart är 17 den största delaren av sig självt.
SGD(100,25) är 25 eftersom 100 är delbart med 25, och 25 är delbart med sig självt. Visserligen har talet 100 två ännu större delare (nämligen 50 och 100), men dessa två är inte delare av 25. Så den största gemensamma delaren blir 25.

Skriv en funktion som beräknar den största gemensamma delaren (SGD) för två givna heltal.

För att lösa detta problem bör man först förstå att SGD(s, m) alltid är samma som SGD(m, s % m)
där m är det minsta talet och s är det största talet. Om ett av talen är 0, är SGD det andra talet.
Exempel: SGD(30, 12) = SGD(12, 30 % 12) = SGD(12, 6) = SGD(6, 12 % 6) = SGD(6, 0) = 6.

Detta sätt att hitta den största gemensamma delaren kallas den euklidiska algoritmen. Den kan enkelt skrivas med hjälp av rekursiva funktionsanrop i C++.

Låt oss kalla funktionen sgd. Så här ska den göra:

• Om ett av talen (s eller m) är 0 ska den returnera det andra talet.
• Annars, ska den returnera sgd(m, s % m).

När din funktion är klar ska du testa den med en main-funktion, så här:

int main() 
{
    int a, b;
    cout << "Ange två tal: ";
    cin >> a >> b;  // Läs in de två talen från användaren
    cout << "Största gemensamma delare (SGD) av " << a << " och " << b << " är: " << sgd(a, b) << endl;
    return 0;
}