C++ program to calculate greatest common divisor [closed]

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?

Photoflash

b = b % a; will never execute – Lowenstern

check the line return b; and ask yourself, how can the program execute b = b % a; if you told it before to return out of this function. – Ichthyosis

if this is homework, you should add the appropriate tag :) – Applicant

for fun, see the GCD algo evaluated at compile time (using templates): blog.emptycrate.com/node/279 – Orford

The fact that your function always claims to return the correct result after one single call should give away that something is wrong. – Cwm

int g(int a, int b){ return b?g(b,a%b):a;} – Solar

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

Hiccup

Recursion should not be used for this. Iteration to find the GCD was good enough for Euclid (Elements circa 300 BCE, book VII, propositions 1 and 2), and it is good enough for you. – Niblick

@EricPostpischil - Recursion makes a simpler solution, I believe, but, ultimately it depends on what the OP wants to do, I just gave my opinion, with a link to source to help. – Hiccup

Answer 2

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

Vaughan

The control may reach end of non-void function. – Halie

the line b = a % b should be a = a % b and vice versa – Mcgee