Greatest Common Divisor

Q: ¿Cuál es la complejidad temporal del algoritmo de Euclides?

Se ejecuta en O(log(min(a, b))) pasos, porque cada dos pasos reduce al menos a la mitad el número más grande. El peor caso es un par de números de Fibonacci consecutivos. Para números de hasta 10^9 , son como máximo 43 pasos, y el algoritmo usa O(1) espacio adicional.

Q: ¿Por qué gcd(a, b) es igual a gcd(b, a % b)?

Escribe a = q × b + r con r = a % b . Un número que divide a a y b divide a a - q × b , que es r . Un número que divide a b y r divide a q × b + r , que es a . Ambos pares tienen los mismos divisores comunes, así que tienen el mismo mayor divisor.

Q: ¿Cuál es el máximo común divisor de dos números coprimos?

Dos números son coprimos cuando su máximo común divisor es 1 , lo que significa que no comparten ningún factor primo. Dos números primos distintos siempre son coprimos, al igual que dos enteros consecutivos cualesquiera, como 8 y 9 .

PrincipianteMatemáticas y simulación

+10

Recibes dos enteros positivos a y b. Devuelve su máximo común divisor: el mayor entero que divide a ambos sin dejar resto.

Por ejemplo, los números que dividen tanto a 8 como a 12 son 1, 2 y 4, así que la respuesta es 4.

Función

gcd(a: integer, b: integer) → integer

ainteger: el primer entero positivo
binteger: el segundo entero positivo
Devuelveinteger: el mayor entero que divide tanto a como b

Restricciones

1 ≤ a ≤ 10⁹
1 ≤ b ≤ 10⁹

Ejemplos

Entrada: a = 12b = 18
Salida: 6
Explicación: Los divisores de 12 son 1, 2, 3, 4, 6 y 12; los divisores de 18 son 1, 2, 3, 6, 9 y 18. El mayor de ambas listas es 6.

Entrada: a = 17b = 5
Salida: 1
Explicación: 17 y 5 son ambos primos y distintos, así que el único divisor que comparten es 1.

Entrada: a = 42b = 42
Salida: 42
Explicación: Un número se divide a sí mismo, y nada mayor que 42 puede dividir a 42, así que el máximo común divisor de 42 y 42 es 42.

+14 pruebas ocultas al enviar

Para ir más allá

¿Puedes ampliar el algoritmo de Euclides para que también devuelva los enteros x y y que cumplen a × x + b × y = gcd(a, b)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

La definición sugiere probar los candidatos uno por uno, y eso funciona con números pequeños. Sin embargo, con a y b de hasta 10^9, dos números grandes que no comparten ningún factor obligan a hacer mil millones de intentos. La observación de Euclides de que gcd(a, b) es igual a gcd(b, a % b) reduce los números tan rápido que ningún par de hasta 10^9 necesita más de 43 pasos.

Cuenta regresivamente desde el número más pequeño

Correcto, pero no termina con las pruebas más grandes

Intuición

Ningún divisor común puede ser mayor que el menor de los dos números, porque un divisor de b es como máximo b. Así que empieza con un candidato d igual a min(a, b) y ve reduciéndolo de uno en uno hasta que divida a ambos. Como pruebas los candidatos empezando por el mayor, el primero que funciona es el máximo.

Para 12 y 18, pruebas 12 (no divide a 18), luego 11, 10, 9, 8 y 7, que no funcionan, y te detienes en 6. El bucle siempre termina, porque 1 divide a todo.

El costo es la cantidad de candidatos. Para 999999937 y 999999929, dos números primos, la respuesta es 1 y el bucle se ejecuta casi 10^9 veces. Eso es demasiado lento para las pruebas más grandes.

Algoritmo

Establece d en el menor de a y b.
Mientras a % d o b % d no sea 0, resta 1 a d.
Devuelve d.

def gcd(a, b):
    d = min(a, b)
    while a % d != 0 or b % d != 0:
        d -= 1
    return d

Algoritmo de Euclides

Intuición

Escribe a = q × b + r, donde r = a % b. Cualquier número que divida tanto a a como a b también divide a r = a - q × b. Cualquier número que divida tanto a b como a r también divide a a = q × b + r. Así que los pares (a, b) y (b, r) tienen exactamente los mismos divisores comunes, y también el mismo máximo.

Reemplaza (a, b) por (b, a % b) y repite hasta que b se convierta en 0. Todo número divide a 0, así que gcd(a, 0) = a y a es la respuesta. Para 12 y 18: (12, 18) se convierte en (18, 12), después en (12, 6), después en (6, 0), y la respuesta es 6. El primer paso intercambia los números por sí solo cuando a es menor, así que nunca necesitas ordenarlos.

Cada dos pasos, el número mayor se reduce al menos a la mitad, así que el bucle se ejecuta O(log(min(a, b))) veces. Las entradas más lentas son números de Fibonacci consecutivos, como 701408733 y 433494437, e incluso estas solo requieren 42 pasos.

Algoritmo

Mientras b no sea 0, calcula r = a % b.
Establece a = b y b = r.
Cuando b llegue a 0, devuelve a.

def gcd(a, b):
    # gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a.
    while b != 0:
        a, b = b, a % b
    return a

Errores comunes y casos límite

El algoritmo es corto, así que los errores se deben a la actualización y a la condición de parada.

Actualizar en el orden incorrecto. a = b seguido de b = a % b calcula b % b, que siempre es 0, y devuelve b. Guarda primero el resto en una variable temporal o asigna ambos valores a la vez.
Devolver b en lugar de a cuando termina el bucle. En ese momento, b es 0.
Detener la cuenta atrás en 2 o empezarla en max(a, b). Lo primero pasa por alto pares coprimos como 17 y 5; lo segundo hace perder tiempo con candidatos que no pueden dividir el número menor.
Usar restas repetidas en lugar del resto. gcd(10^9, 1) requiere entonces mil millones de restas; % las hace todas en un solo paso.

Preguntas frecuentes4

¿Cuál es la complejidad temporal del algoritmo de Euclides?

Se ejecuta en O(log(min(a, b))) pasos, porque cada dos pasos reduce al menos a la mitad el número más grande. El peor caso es un par de números de Fibonacci consecutivos. Para números de hasta 10^9, son como máximo 43 pasos, y el algoritmo usa O(1) espacio adicional.

¿Por qué gcd(a, b) es igual a gcd(b, a % b)?

Escribe a = q × b + r con r = a % b. Un número que divide a a y b divide a a - q × b, que es r. Un número que divide a b y r divide a q × b + r, que es a. Ambos pares tienen los mismos divisores comunes, así que tienen el mismo mayor divisor.

¿Cuál es la diferencia entre el MCD y el MCM?

El máximo común divisor es el número más grande que divide a ambas entradas; el mínimo común múltiplo es el número más pequeño que es divisible por ambas entradas. Están relacionados mediante gcd(a, b) × lcm(a, b) = a × b, así que, una vez que tienes el MCD, el MCM es a / gcd(a, b) × b.

¿Cuál es el máximo común divisor de dos números coprimos?

Dos números son coprimos cuando su máximo común divisor es 1, lo que significa que no comparten ningún factor primo. Dos números primos distintos siempre son coprimos, al igual que dos enteros consecutivos cualesquiera, como 8 y 9.

Python

def gcd(a, b):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

a = 12
b = 18

Esperado