Para ser honesto, nunca aprendí esto en la escuela. Pero encontré varios enlaces al algoritmo euclidiano en una búsqueda en la web. La entrada de Wikipedia parecía un poco complicada y técnica, para absorber. Encontré un enlace aquí: Teoría de números – Algoritmo de Euclides que, comenzando en el cuarto párrafo, expuso el algoritmo de manera bastante simple.
Es posible que haya encontrado un secreto sobre los múltiplos del número 3. Básicamente, sabe que un número es divisible por 3 si la suma de sus dígitos es un múltiplo de tres. Para un número muy grande, la suma de los dígitos puede no reconocerse como un múltiplo de tres, por lo que esos dígitos pueden sumarse y probarse para ver si son múltiplos de tres (o 3, en sí). Esto se puede repetir.
El truco con múltiplos de 3 no tiene casi nada que ver con el algoritmo euclidiano. Excepto que la característica común es devolver el resultado de la técnica a la técnica, hasta que la respuesta sea evidente.
- ¿La programación competitiva se volverá aún más difícil?
- ¿En qué situación no debemos usar la tabla Hash?
- ¿Es posible elegir aleatoriamente un número de (0 a infinito), de modo que cada número tenga la misma probabilidad de ser elegido?
- Cómo abordar el problema 'Mapa intergaláctico' (IM) en SPOJ usando Max Flow
- Cómo hacer un algoritmo de filtrado basado en contenido de Python
- El algoritmo euclidiano nos hace comenzar con los dos números como un par.
- El número más pequeño del par se divide en el número más grande, produciendo un cociente y un resto.
- Si el resto es cero, nuestro divisor es el máximo común divisor.
- Si el resto es mayor que 1, entonces el número más pequeño y el resto se usan para formar un nuevo par de números para repetir el proceso.
- Si el resto es exactamente 1, entonces el algoritmo se detiene. El máximo común divisor es 1, que define el par original como “co-prime”.
Euclides fue muy físico y geométrico en su enfoque. Algunos de los enlaces al algoritmo se refieren a “tomar medidas” de un número como una longitud, en términos de la otra longitud.
En este caso, esas longitudes serían 75 y 55.
Entonces
Paso 1: Nuestro primer par es (75, 55)
Paso 2: El número más pequeño, 55, se divide en 75. El cociente es 1. El resto es 20.
Los pasos 3 y 5 no se aplican. El paso 4 sí. Nuestro nuevo par es ahora (55, 20). Regresar al paso 2.
Paso 2: dividimos 20 en 55, lo que hace 2 veces, el resto 15.
El paso 4 se aplica nuevamente: formamos un nuevo par a partir de nuestro número más pequeño, 20, y el resto de 15. (20, 15). Regresar al paso 2:
Paso 2: dividimos 15 en 20. Va una vez, el resto 5.
El paso 4 se aplica nuevamente: formamos un nuevo par de 15 y 5. Volver al paso 2 con (15, 5)
Paso 2: dividimos 5 en 15 y encontramos que entra de manera uniforme. El resto es 0.
El paso 3 se aplica esta vez. Nuestro mayor divisor común es 5.
Nos detenemos con nuestra respuesta.
Verifiquemos nuestros resultados de otra manera.
Los factores primos de 55 son 5 x 11.
Los factores primos de 75 son 5 x 5 x 3.
La intersección de {5, 11} y {5, 5, 3} es solo {5}. El MCD también conocido como máximo factor común es 5.
