Programa Python para encontrar el mcd de dos números

Dados dos números. La tarea es encontrar el MCD de los dos números.

Usando STL:

En Python, el módulo de matemáticas contiene una serie de operaciones matemáticas, que se pueden realizar con facilidad usando el módulo. La función math.gcd() calcula el máximo común divisor de 2 números mencionados en sus argumentos.

Sintaxis: matemáticas.gcd(x, y)

Parámetro:

x : Entero no negativo cuyo mcd debe calcularse.

y : Entero no negativo cuyo mcd debe calcularse.

Devuelve: un valor entero absoluto/positivo después de calcular el GCD de los parámetros dados x e y.

Excepciones: cuando tanto x como y son 0, la función devuelve 0, si algún número es un carácter, se genera un error de tipo.

# Python code to demonstrate the working of gcd()
# importing "math" for mathematical operations
import math
  
# prints 12
print("The gcd of 60 and 48 is : ", end="")
print(math.gcd(60, 48))

The gcd of 60 and 48 is : 12

Usando recursividad:

# Python code to demonstrate naive
# method to compute gcd ( recursion )
  
  
def hcf(a, b):
    if(b == 0):
        return a
    else:
        return hcf(b, a % b)
  
a = 60
b = 48
  
# prints 12
print("The gcd of 60 and 48 is : ", end="")
print(hcf(60, 48))

The gcd of 60 and 48 is : 12

Usando el algoritmo de Euclides:

El algoritmo de Euclides (o algoritmo de Euclides) es un método para encontrar eficientemente el máximo común divisor (MCD) de dos números. El MCD de dos enteros X e Y es el número más grande que divide tanto a X como a Y (sin dejar resto).

Pseudo Código del Algoritmo-

1. Sean a, b los dos números
2. una modificación b = R
3. Sean a = b y b = R
4. Repita los pasos 2 y 3 hasta que a mod b sea mayor que 0
5. mcd = b
6.  Finalizar

# Recursive function to return gcd of a and b
def gcd(a, b):
  
    # Everything divides 0
    if (a == 0):
        return b
    if (b == 0):
        return a
  
    # base case
    if (a == b):
        return a
  
    # a is greater
    if (a > b):
        return gcd(a-b, b)
    return gcd(a, b-a)
  
# Driver program to test above function
a = 98
b = 56
if(gcd(a, b)):
    print('GCD of', a, 'and', b, 'is', gcd(a, b))
else:
    print('not found')

GCD of 98 and 56 is 14