Tornar

Algoritme d'Euclides

Euclides va ser un gran matemàtic i filòsof de l'antiguitat. Va idear un procediment per tal d'obtenir el màxim comú divisor (MCD) de dos nombres. 

Donats dos nombres enters A i B es divideix el més gran entre el més petit. Si la resta R de la divisió es 0, el divisor B és el MCD, en cas contrari, B es converteix en dividend i R en divisor. Tornem a fer la divisió, si la resta d'aquesta nova divisió es 0, el divisor R és el MCD, en cas contrari, el divisor es converteix en dividend i la resta de la divisió en divisor, i tornem a fer la divisió. Fent això successivament trobarem alguna vegada resta 0, en aquest moment, el divisor de la divisió serà el MCD.

El fitxer d'entrada contindrà els dos nombres enters i el fitxer de sortida contindrà el MCD.

Exemple:

Tornar