ALGORITME D´EUCLIDES

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:

MCD(160, 60)

160 entre 60 dóna resta 40

60 entre 40 dóna resta 20

40 entre 20 dóna resta 0, per tant 20 és el MCD

fitxer d'entrada:

160

fitxer de sortida