C++ programa para calcular el mayor divisor común

Question

He comenzado este programa para calcular el divisor común más grande. Esto es lo que tengo hasta ahora:

#include <iostream> 
#include <math.h> 
using namespace std; 
int getGCD(int a, int b) 
{ 
    a = a % b; 
    if (a == 0) 
    { 
     return b; 
     b = b % a; 
    } 
    if (b == 0) 
    { 
     return a; 
    } 
} 
int main() 

{ 
    int x, y; 
    cout << "Please enter two integers x and y, for GCD calculation" << endl; 
    cin >> x >> y; 
    cout << "The GCD of " << x << "and " << y << " is" << getGCD(x, y) << endl; 
    return 0; 
} 

siempre me dan un 0 para el MCD. ¿Qué estoy haciendo mal?

Answer 1

Debería estar dando vueltas para encontrar esto, y puede serle útil si coloca, con algunas ecuaciones, su algoritmo de cómo debería funcionar esto.

Pero tiene dos problemas que veo, a menos que llame esto dentro de otro ciclo.

Usted está regresando en ambos casos, ya sea el if o el otro, así que solo pasa por aquí una vez.

Además, esta parte no tiene sentido, ¿por qué modificar el valor b después de hacer un return?

  return b; 

      b = b%a; 

Debería utilizar recursion para esto, por cierto.

http://rosettacode.org/wiki/Greatest_common_divisor#Recursive_Euclid_algorithm

Answer 2

int getGCD(int a, int b) { 

// Aquí tenemos que comprobar si b == 0 retorno de la implementación

if (b == 0) { 
     return a; 
    } 
    return gcd(b, a % b); 
} 

algoritmo de Euclides