C++ program to calculate greatest common divisor

Question

I have started this program to calculate the greatest common divisor. This is what I have so far:

#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;
}

I always get a 0 for the GCD. What am I doing wrong?

Answer 1

You should be looping through to find this, and it may help if you put, with some equations, your algorithm for how this should work.

But you have two problems I see, unless you are calling this inside of another loop.

You are returning in both cases, either the if or else, so you only go through here once.

Also, this part makes no sense, why modify the b value after doing a return?

          return b;

          b = b%a;

You should be using recursion for this, btw.

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