Máximo factor común de Python (HCF / GCD)
Calcule el máximo común divisor (HCF) o el máximo común divisor (MCD) de dos números utilizando el algoritmo euclidiano.
Descripción general
El máximo común divisor (HCF), también conocido como máximo común divisor (MCD), es el mayor entero positivo que divide dos o más números enteros sin dejar resto.
El algoritmo euclidiano es un método extremadamente eficiente para calcular HCF. Afirma que el MCD de dos números también divide su diferencia.
En Python, implementamos esto de forma iterativa usando un bucle while donde reemplazamos continuamente el número mayor con el resto de su división.
Código y salida de ejecución
Implementación de bucle euclidiano para encontrar HCF/MCD de dos números.
def find_gcd(a, b):
# Euclidean Algorithm
while b != 0:
a, b = b, a % b
return a
print("GCD of 36 and 60 is:", find_gcd(36, 60))
print("GCD of 17 and 5 is: ", find_gcd(17, 5))GCD of 36 and 60 is: 12
GCD of 17 and 5 is: 1Implementación paso a paso
- Simplificación de fracciones y motores matemáticos.
- Algoritmos de criptografía (como la generación de claves privadas RSA)
- Diseño de cronogramas periódicos de eventos.
Preguntas frecuentes
¿Python tiene una función GCD incorporada?
¡Sí! La biblioteca estándar de Python contiene `math.gcd(a, b)` que utiliza una implementación C compilada internamente.
Temas relacionados
Encuentre el mínimo común múltiplo (MCM) de dos números usando su relación HCF en Python.
Script de calculadora simple de PythonConstruya una calculadora básica en Python. Aprenda a mapear operadores matemáticos, tomar flujos de ejecución de usuarios y manejar la lógica de forma nativa.