Recursive GCD Function


Program Listing

RecursiveGCD.cpp

/****************************************************************************
*                                                                           *
*   Program:    RecursiveGCD                                                *
*                                                                           *
*   Purpose:    This program will test the GCD() and LCM() functions        *
*                                                                           *
****************************************************************************/

//  Header files

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

//  Functions prototypes

int GCD(int a, int b);
int LCM(int a, int b);

/****************************************************************************
*                                                                           *
*   Function:   main                                                        *
*                                                                           *
*   Purpose:    To test the GCD() and LCM() functions                       *
*                                                                           *
****************************************************************************/

int main() {

//  Get two integers from the user

    cout << "Enter two integers:  " << flush;
    int x, y;                                   // Two integers for the test
    cin >> x >> y;

//  Find the greatest common divisor and print it

    int div = GCD(x, y);                        // Get the g.c.d.
    cout << "The g.c.d. of " << x << " and " << y << " is " << div << endl;

//  Find the least common multiple and print it

    int mult = LCM(x, y);                       // Get the l.c.m.
    cout << "The l.c.m. of " << x << " and " << y << " is " << mult << endl;
    
    return 0;
}

/****************************************************************************
*                                                                           *
*   Function:   GCD                                                         *
*                                                                           *
*   Purpose:    To find the greatest common divisor of two integers         *
*                                                                           *
*   Note:       This function computes the GCD recursively                  *
*                                                                           *
****************************************************************************/

int GCD(int a, int b) {

//  Make sure integers are nonnegative

    a = abs(a);                                 // Make first int nonneg
    b = abs(b);                                 // Make second int nonneg

//  Make sure at least one of them is positive

    if (b == 0)                                 // Divisor is zero
        return a;                               // Return other integer
    else                                        // Divisor is nonzero
        return GCD(b, a % b);                   // Continue Euclidean algorithm
}

/****************************************************************************
*                                                                           *
*   Function:   LCM                                                         *
*                                                                           *
*   Purpose:    To find the least common multiple of two integers           *
*                                                                           *
*   Note:       This function uses the GCD to find the LCM                  *
*                                                                           *
****************************************************************************/

int LCM(int a, int b) {

//  Make sure a and b are not both 0

    if (a == 0 && b == 0)
        return 0;
    else
        return (a*b)/GCD(a, b);                     
}

Sample Run

Enter two integers:  321 987
The g.c.d. of 321 and 987 is 3
The l.c.m. of 321 and 987 is 105609



Return to Lectures page


e-mail me at robbk@hsc.edu

This page was last modified on Tue Dec 7 16:04:41 1999 .

URL: http://people.hsc.edu/faculty-staff/robbk/Coms261/Examples/RecursiveGCD.html

Return to Coms 261 home page