Share
Explore BrainMass

Greatest Common Divisor (GCD) in C++ with Example

I need the following problem in C++ with a recursive function and a driver programe to test the function ?

* A recursive program to calculate the Greatest
Common Divisor of two integers using the Euclidean Method.
The algorithm in non-recursive form is as follows:
EuclidGCD(a,b) {
while (b not 0) {
swap(a,b)
b = b mod a;
}
return a;
}
example:
gcd(356,96) = gcd(96,68) = gcd(68,28) = gcd(28,12) = gcd(12,4) = gcd(4,0) = 4
*/

#include <stdio.h>
#define DEBUG 1

int gcd(int a, int b){
if (b==0) return a;
#ifdef DEBUG
printf("gcd(%d, %d)= ", b,a%b);
#endif
gcd(b, a%b);

}

int main(){
int a=356, b=96;

printf(" Please Enter two integers for their GCD :");
scanf("%d%d",&a,&b);
printf("%d",gcd(a,b));
return 0;
}

Attachments

Solution Preview

The following is a c++ version of the above program to calculate Greatest Common Divisor of two integers.

#include <iostream>
...

Solution Summary

Solution of the problem is given in C++ with a recursive function and a driver program to test the function

$2.19