Massimo Comun Divisore

/*L’algoritmo di Euclide `e un algoritmo per trovare il massimo comun divisore (in-
dicato di seguito con MCD tra due numeri interi.*/
/* http://juni0rblog.blogspot.com/ */
/* juni0r87@yahoo.it */

#include

int MCD1(int a, int b);

int main()
{
int x;
int y;
scanf("%d%d", &x,&y);
printf("%d", MCD1(x,y));
return 0;
}

int MCD1(int a, int b)
{
int temp;

/*PREC: m,n!=0 */

/* MCD(a, b) = a se b = 0 b se a = 0 */
if (a == 0)
return b;
if (b == 0)
return a;

/* MCD(a, b) = MCD(b,a mod b) se a > b > 0 */
if (a < b)
{
while (b%a != 0)
{
temp = b;
b = a;
a = temp%a;
}
return a;
}
else
/* MCD(a, b) = MCD(a, b mod a) se b > a > 0 */
{
while (a%b !=0)
{
temp = a;
a = b;
b = temp%b;
}
return b;
}
}