Algoritmo Euclidiano

Hoy en clase vimos lo que es un Algoritmo euclideano, y la maestra nos dio una brebe explicacion de como este funciona.

Definicion:
Método para encontrar el máximo factor común de dos enteros. Se divide el número mayor entre el número menor. Se repite la división, utilizando el residuo como divisor, hasta que el residuo se convierte en cero. El último residuo diferente a cero es el máximo factor común de los dos enteros

La explicacion es asi:
 A    %    B = c
56    %    35 = 21   -->56 - 1X35 (56/35)
35    %    21 = 14   -->35 - 1X21 (35/21)
21    %    14 = 7     -->21 - 1X14 (21/14)
14    %     7 = 0

Ahora en Codigo.

using namespace std;

int mcd(int x , int y){
int t;
x = (x < 0) ? -x:x; 

y = (y < 0) ? -y:y; 

t = (x < y) ? x : y; 

while ( (x % t) || (y % t))

       --t; 

return t;

}

int euc(int x,int y){ 

return (!y) ? x : euc(y,x%y); 

}

int main() 

{

int x,y; 

cout << "x: "; 

cin >> x;
cout << "y: "; 

cin >> y;
cout << "MCD: " << mcd(x,y) << endl; 

cout << "MCD (euclides): " << euc(x,y) << endl; 

system("PAUSE"); 

}

Consola