C++ program to calculate greatest common divisor [closed]
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 << "Pleas开发者_如何学Ce 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?
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
int getGCD(int a, int b) {
//here we need to check if b == 0 return a
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
Euclid's Algorithm Implementation
精彩评论