Si el objetivo es encontrar el máximo común divisor (MCD) de dos enteros, el medio más eficiente se conoce desde hace un par de miles de años: el Algoritmo Euclidiano. Se puede hacer solo por sustracción o con aritmética modular.
Aquí está mi explicación. (¡ Esto está tomado de mi propio sitio, así que solo me estoy plagiando! – Quora colapsó mi respuesta cuando solo proporcioné un enlace ) .
Las explicaciones del algoritmo euclidiano para encontrar el máximo divisor común de dos enteros a menudo parecen largas y complicadas. La idea es, de hecho, bellamente simple. Todo lo que es es un proceso de sustracción repetida, llevando el resultado hacia adelante cada vez hasta que el resultado sea igual a la cantidad que se resta. Si la respuesta es mayor que 1, hay un MCD (además de 1). Si la respuesta es 1, no hay un divisor común (además de 1), por lo que ambos números son primos entre sí, o primos relativos.
El algoritmo sustractivo es simplemente esto, donde ‘enjuaga y repite’ los bucles internos siempre que a no sea igual a b .
- ¿Son realmente los ‘problemas de Landau’ un problema?
- ¿Qué número es divisible por la mayoría de los números en relación con su tamaño?
- ¿Existen números primos en aritmética modular?
- ¿Cuál es el significado de las funciones de Jacobi theta?
- ¿Es posible que la conjetura de Goldbach sea verdadera pero no demostrable?
Hacer mientras a b
Hacer mientras a> b
c = a – b
a = c
Lazo
Hacer mientras b> a
c = b – a
b = c
Lazo
Lazo
Lo que queda es que aob es igual a 1, sin MCD, o aob es mayor que 1, un MCD.
Quizás la simplicidad del algoritmo se ve oscurecida por la práctica habitual de usar la división modular. De hecho, no se requiere una división modular, ¡y los griegos ciertamente no la usaron! Sin embargo, el algoritmo euclidiano también es una gran demostración del poder de la aritmética modular.
Pruebe el siguiente código VBA * con, por ejemplo, un número de 10 dígitos y un número de 3 dígitos. El método de resta tomará miles de iteraciones para producir un resultado. (Si obtiene un desbordamiento, probablemente sea porque ha excedido el límite del cuadro de lista). Luego, intente reemplazar la resta con las dos líneas de división modular en el código a continuación, y vea cómo se logra el resultado en solo unas pocas iteraciones y un Fracción de segundo.
Opción explícita
Subcomando privado1_Click ()
Atenuar a como variante, b como variante, c como variante
List1.Clear
Si Val (Texto1)> Val (Texto2) Entonces
a = CDec (Val (Texto1))
b = CDec (Val (Texto2))
Más
a = CDec (Val (Texto2))
b = CDec (Val (Texto1))
Terminara si
Si a = 0 Or b = 0, salga de Sub
Repetir:
Hacer mientras a> b
c = a – b ‘eliminar para modular
” ” ” ” ‘Para División Modular’ ” ” ” ” ” ”
‘Si b = 0 Entonces Ir a Finalizar
‘c = a Mod b
” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ”
List1.AddItem Trim $ (a) + “-” + Trim $ (b) + “=” + Trim $ (c)
List1.ListIndex = List1.ListCount – 1
a = c
Me.Refresh
DoEvents
Lazo
Hacer mientras b> a
c = b – a ‘eliminar para modular
” ” ” ” ‘Para División Modular’ ” ” ” ” ” ”
‘Si a = 0 Entonces Ir a Finalizar
‘c = b Mod a
” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ”
List1.AddItem Trim $ (b) + “-” + Trim $ (a) + “=” + Trim $ (c)
List1.ListIndex = List1.ListCount – 1
b = c
Me.Refresh
DoEvents
Lazo
Si a b, entonces vaya a repetir
” ” ” ” ‘Para División Modular’ ” ” ” ” ” ”
‘Terminar:
‘List1.AddItem “GCD =” + Str $ (b)
” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ” ”
List1.AddItem “GCD =” + Str $ (a) ‘remove for modular!
List1.Selected (List1.ListCount – 1) = Verdadero
End Sub
* Para ejecutar el código, necesitará un formulario de MS Office habilitado para macros con dos cuadros de texto, un cuadro de lista y un botón de comando.