IN C++ Greatest Common Divisor The greatest common divisor (GCD) of two integers
ID: 3683589 • Letter: I
Question
IN C++
Greatest Common Divisor The greatest common divisor (GCD) of two integers a and b is the largest positive integer that divides both a and b. The Euclidean algorithm for finding the greatest common divisor of a and b is as follows. Assume neither number is 0, and let a be the larger number in absolute value. Divide a by b to obtain the integer quotient q and remainder r. such that a = bq + r. It is known that GCD(a,b) = GCD(b,r), so replace a with b and b with r, then repeat all the steps until the remainder is 0. Since the remainders are decreasing, eventually a 0 remainder will result. The last non-zero remainder is the greatest common divisor of a and b, i.e., GCD(a,b). The following example illustrates the process. So, the GCD of the original two numbers - 1260 and 198 - is 18. Write a program that includes a user-defined function named GCD that calculates and returns the greatest common divisor of two integer arguments. Do not use the >> orExplanation / Answer
#include <iostream>
using namespace std;
int GCD(int a, int b);
int main()
{
int a, b;
cout << "Enter two integers values: ";
cin >> a >> b;
cout << "Greater common division is " << a << " & " << b << " is: " << GCD(a, b);
return 0;
}
int GCD(int a, int b)
{
if (b!=0)
return GCD(b, a%b);
else
return a;
}