MCD de dos números es el número más grande que los divide a ambos. Una forma sencilla de encontrar el MCD es factorizar ambos números y multiplicar factores comunes.
C
// C program to demonstrate Basic Euclidean Algorithm
#include <stdio.h>
// Function to return gcd of a and b
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Driver program to test above function
int main()
{
int a = 10, b = 15;
printf("GCD(%d, %d) = %d\n", a, b, gcd(a, b));
a = 35, b = 10;
printf("GCD(%d, %d) = %d\n", a, b, gcd(a, b));
a = 31, b = 2;
printf("GCD(%d, %d) = %d\n", a, b, gcd(a, b));
return 0;
}
Producción:
GCD(10, 15) = 5 GCD(35, 10) = 5 GCD(31, 2) = 1
Complejidad de tiempo: O(Log min(a, b))
Espacio auxiliar: O(1)
Consulte el artículo completo sobre algoritmos euclidianos básicos y extendidos para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA