Supongamos que necesitamos encontrar el máximo común divisor (MCD), también llamado el máximo común divisor (HCF) de dos números naturales [matemática] a [/ matemática] y [matemática] b [/ matemática].
Por supuesto, podemos encontrar los factores de los dos números y luego determinar el factor común más alto.
Sin embargo, a medida que los números aumentan (digamos 1555663288198292), la factorización se vuelve ineficaz.
Aquí es donde el algoritmo de Euclides viene a nuestro rescate.
- Cómo encontrar soluciones enteras de una función en un rango dado
- Cómo crear un algoritmo
- Necesito generar todas las combinaciones posibles de N parámetros. ¿Hay una forma más rápida (más eficiente) de hacerlo que incrustar N para bucles?
- Si viaja al extranjero, ¿elegiría una aplicación de traducción humana para ayudarlo a resolver un problema de idioma?
- ¿Es determinante un operador que opera en un conjunto de números?
Simplemente dice que si dos números naturales [matemática] a [/ matemática] y [matemática] b [/ matemática] tienen un número natural [matemática] c [/ matemática] ese es su máximo divisor común, es decir, el mayor número que divide a ambos, luego [math] c [/ math] también dividirá [math] ba [/ math] suponiendo que [math] b> a [/ math].
Entonces podemos reemplazar el número más grande, aquí [matemáticas] b [/ matemáticas], con la diferencia [matemáticas] ba [/ matemáticas].
Es decir, el MCD de [matemáticas] a [/ matemáticas] y [matemáticas] b [/ matemáticas] también será el MCD de [matemáticas] a [/ matemáticas] y [matemáticas] ba [/ matemáticas]. Esto nos ayudará a reducir el tamaño de nuestro problema. Entonces podemos seguir reemplazando el número más grande con la diferencia absoluta entre los números hasta que nos queden dos números iguales. Este número igual es el MCD requerido.
Suponga que [matemáticas] a [/ matemáticas] = 10 y [matemáticas] b [/ matemáticas] = 16
MCD (10,16) = MCD (10,6) = MCD (4,6) = MCD (4,2) = MCD (2,2) = 2
Podemos optimizar aún más el algoritmo reemplazando el número más grande con el resto que queda, cuando el número más grande se divide por el más pequeño.
El MCD se obtiene cuando llegamos a un punto donde el resto se vuelve cero después de reemplazos sucesivos.
es decir, MCD (10,16) = MCD (6,10) = MCD (6,4) = MCD (2,4) = 2 (ya que el resto se convirtió en 0)
¡Salud! 🙂