Màxim comú divisor

El mètode d’Euclides per calcular el màxim comú divisor de dos nombres es basa en les propietats següents:

• \(mcd(a,b)=mcd(b,a)\)

• Si \(a>b\) llavors \(mcd(a,b)=mcd(a-b,b)\)

• Si \(b>a\) llavors \(mcd(a,b)=mcd(a,b-a)\)

• \(mcd(a,a)=a\)

En el fitxer mcd.py (mòdul mcd), dissenyeu la funció recursiva:

mcd.mcd(x, y)

A partir de dos valors enters x i y, retorna el seu màxim comú divisor.

Per exemple:

>>> mcd (15,25)
5
>>> mcd (36, 90)
18
>>> mcd(453, 87)
3
>>> mcd(462, 1071)
21

Nota

Disposeu de jocs de prova al fitxer mcd.txt.

Solució

Disposeu d’una solució al fitxer mcd.py.