Nos aprovechamos de la propiedad gcd(a, b)= gcd(b, a % b) y dado que el gcd(c, 0)= c podemos definir recursivamente la función gcd(a, b) de la siguiente manera:
GCD
int gcd (int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
O (log min(a, b))
int gcd (int a, int b) {
while (b) {
a %= b;
swap(a, b);
}
return a;
}
El mínimo común múltiplo (LCM) de dos números se relaciona directamente con su GCD mediante la siguiente fórmula:
LCM
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}