C ++ program to calculate the greatest common divisor

Question

I started this program to calculate the greatest common factor. 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 0 for GCD. What am I doing wrong?

Answer 1

You have to go through a cycle to find this, and it can help if you put your algorithm with some equations, how it should work.

But you have two problems that I see if you do not call this inside another loop.

You return in both cases, either if or otherwise, so you only go here once.

In addition, this part does not make sense, why change the value of b after doing return ?

  return b; b = b%a; 

You must use recursion for this, btw.

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

Answer 2

 int getGCD(int a, int b) { 

// here we need to check if b == 0 will return a

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

Euclidean algorithm execution