A Programozás Wiki wikiből

Az euklidészi algoritmus segítségével két szám legnagyobb közös osztója határozható meg.

Egy példa megvalósítás az osztási módszer alkalmazásával:

  Be: a, b (a > b)
  Eljárás LNKO
     Ciklus amíg b > 0
        t := b
        b := a mod b
        a := t
     Ciklus vége
   visszaad a
  Eljárás vége

Megfigyelhetjük, hogy az algoritmus akkor is működik, ha az a bemenet kisebb, mint a b bemenet, feltéve, hogy mindkettő pozitív. A ciklus első menete ekkor megcseréli az a és b értékét, hiszen a mod b értéke egyenlő a-val, ha a<b

[szerkesztés] Példák különböző programnyelveken

[szerkesztés] C++ példa

int lnko(int a, int b) {
   int tmp;
 
   if (a<0) a= -a;
   if (b<0) b= -b;
   while(b > 0) {
      tmp = b;
      b = a % b;
      a = tmp;
   }
   return a; // eredmény vissza
}

[szerkesztés] Python példa

def lnko(a, b):
    while b>0:
        a, b = b, a%b
    return a   # eredmény vissza