Calcular el MCD.

[josefinakey]

Hola gente, soy muy nueva en esto de la programacion y tengo problemas para hallar el mcd de dos números ingresados por consola. Seguramente alguno de ustedes puede darme una mano.

Esto es lo que pude hacer:

Código Python:

a=int(raw_input('ingrese el primer numero:'))
b=int(raw_input('ingrese el segundo numero:'))
 
if a==0:
  print 'el mcd es', b
  
if b==0:
  print 'el mcd es', a
  
while a!=b:
  a%b
  if a%b==0:
    print
    
  elif a!=0 and b!=0:
    b%a
    print
 

Ojala puedan ayudarme.
Saludos

[razpeitia]

No se de donde sacaste ese algoritmo, pero ese no es el algoritmo para sacar el MCD.
El algoritmo que se usa para sacar el MCD (GCD en ingles) es el algoritmo de euclides.

Ahora una implementacion en python sería la siguiente:

Código Python:

def mcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
 

También puedes tener su implementación recursiva

Código Python:

def mcd(a, b):
    if b == 0:
        return a
    return mcd(b, a % b)
 

Si es el caso que sea una tarea (que ciertamente lo dudo) puede usar la siguiente función predefinida:

Código Python:

from fractions import gcd
 

[josefinakey]

Estoy trabajando con un libro de programación y dice: "Dados dos números naturales ay b comprobar si b es cero. Si es así, a es el mcd. Si no, calcular c, el resto de dividir a entre b. Sustituir a por b y b por c y repetir el proceso"

Intente hacer eso, pero no supe como llevarlo a python.

No es una tarea, estoy tratando de aprender a programar en python.

MUCHAS GRACIAS POR TU AYUDA :)

[AlvaroG]

josefinakey,
Los algoritmos de cálculo de MCD requieren que a sea mayor que b. Lo menciono porque has intentado en tu código original comprobar que "a" no sea cero, pero el algoritmo no funciona si a < b.

El enunciado que pusiste para el algoritmo de euclides es recursivo. Traducido lo más exactamente posible a Python, sería:

Código Python:

def mcd(a, b):
    if b == 0:
        return a
    else:
        c = a % b
        return mcd(b,c) # "sustituir a por b y b por c y repetir el proceso"
 

Lo cual, si eliminamos pasos superfluos, es exactamente lo que te escribió razpeitia antes.

A propósito, me gusta esta forma del método recursivo (aunque prefiero el método iterativo):

Código Python:

def mcd(a, b):
    return a if b == 0 else mcd(b, a%b)
 

Saludos.