Question

1. (10 points) GCD Algorithm The greatest common divisor of two integers a and b where a 2 b is equal to the greatest common divisor of b and (a mod b). Write a program that implements this algorithm to find the GCD of two integers. Assume that both integers are positive. Follow this algorithm: 1. Call the two integers large and small. 2. If small is equal to 0: stop: large is the GCD. 3. Else, divide large by small. Call the remainder small. The previous small becomes large 4. Go back to steps 2 For example, say the two integers are 160 and 75: large 160 % 75 10 75 % 10-5 10%5-0 5 small o end (GCD is 5) In your program, prompt the user for two integers large and small. After the GCD has been computed, write it out to the monitor. The user dialog will look something like this: Enter large integer: 160 Enter small integer: 75 GCD: 5

Answer 1

#include <iostream>
//you have not specified the language..
//i have written this with basic syntax so that you can understand the logic

using namespace std;
//method that returns the gcd
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b%a, a);//performing mod
}
//testing
int main()
{
int a, b;
//reading input
    cout<<"Enter large value:";
    cin>>a;
    cout<<"Enter small value:";
    cin>>b;
    cout<<"GCD :"<<gcd(a,b)<<endl;
return 0;
}

output:

Enter large value:160
Enter small value:75
GCD :5

Process exited normally.
Press any key to continue . . .