Greatest Common Divisor The greatest common divisor (GCD) of two integers a and

Q: Greatest Common Divisor The greatest common divisor (GCD) of two integers a and

//header files #include #include using namespace std; // function prototype int GCD(int a, int b); // main function int main() { while(true) { // declare variables int a, b; // getting input from user cout > a >> b; cout

ID: 3669082 • Letter: G

Question

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 this 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 then b with r, and repeat all the steps until the remainder is 0.

Since the remainders are decreasing, eventually a 0 remainder will result. The last nonzero remainder is the greatest common divisor of a and b, i.e., GCD(a,b). For example,

1260 = 198 x 6 + 72 GCD(1260,198) = GCD(198,72)

198 = 72 x 2 + 54 GCD(198,72) = GCD(72,54)

72 = 54 x 1 + 18 GCD(72,54) = GCD(54,18)

54 = 18 x 3 + 0 GCD(54,18) = 18

So the GCD of the original two numbers, namely 1260 and 198, is 18.

Write a C++ program that includes a user-defined function named GCD that will calculate and return the greatest common divisor of two integer arguments. Do not use the >> or << operations in your function!:

int GCD(int, int);

Your main program should read two integers from the console, call GCD to calculate the greatest common divisor, and display the results on the terminal display. Include a continuation loop that will continue this process as long as the user wishes.

Notes: (i) If either of the GCD function arguments is negative, replace it with its absolute value. (ii) above, a represents the larger of the two values (in absolute value). However, do not assume that a will always be the first argument. Rather, since the larger value could be either of the two input arguments to the GCD function; your function must check the arguments values, and assign a the larger of the two arguments (in absolute value), and b the smaller (again, in absolute value). (iii) The GCD of two numbers plays an important role in a number of real world areas, such as certain types of encryption (see the Challenge Problem).

Examples:

enter two integer values: 1 17 greatest

common divisor is: 1 continue? (y/n): y

enter two integer values: 9 15 greatest

common divisor is: 3 continue? (y/n): n

Explanation / Answer

//header files
#include <iostream>
#include <cmath>

using namespace std;

// function prototype
int GCD(int a, int b);

// main function
int main() {
   while(true) {
       // declare variables
       int a, b;

       // getting input from user
       cout << "enter two integer values: ";
       cin >> a >> b;

       cout << "greatest common divsor is: " << GCD(a,b) << endl;

       char userInput;
       cout << "continue? (y/n): ";
       cin >> userInput;

       // y is not equal to input then break the condition
       if('y' != userInput) {
           break;
       }
   }
   return 0;
}

// GCD
int GCD(int a, int b) {
   a = abs(a);
   b = abs(b);
   while(true) {
       int r = a % b;
       if(0 == r) break;
       a = b;
       b = r;
   }
   return b;
}

Sample output

enter two integer values: 1 17
greatest common divsor is: 1
continue? (y/n): y
enter two integer values: 9 15
greatest common divsor is: 3
continue? (y/n):

Navigate

Greatest Common Divisor (GCD) The greatest common divisor (GCD) of two integers

Greatest Common_Divisor (Chapter 7, Pr 6) The greatest common divisor of two int

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Greatest Common Divisor The greatest common divisor (GCD) of two integers a and

Question

Explanation / Answer

Related Questions

Navigate