14. Write a function that uses Euclid\'s algorithm to calculate the greate commo

Question

14. Write a function that uses Euclid's algorithm to calculate the greate
common divisor of its two integer arguments where both arguments
are positive and the first argument should be greater than or equal to
the second. For example, euclid( 10, 2) is 2, euclid( 20, 12) is _.
Euclid's algorithm (int euclid(int m, int n)) forfindingthegreat-
est common divisor of m and n follows:
if (m is less than n) // the arguments are in the
                             // wrong order
return the result of euclid(n, m) // reverse the
                                                // arguments
else if (n divides m) // n is a divisor of m
return n
else
return euclid(n, remainder of m divided by n)

The above algorithm is called a recursive algorithm because function
euclid calls itself (a legal operation in C++). If the first condition is
true, the arguments need to be reversed before the greatest common
divisor can be found by recalling function euclid. If the second con-
dition is true, the smaller argument, n, must be the divisor we're
seeking. Otherwise, the result can be determined by recalling func-
tion euclid to find the greatest common divisor of n and the remain-
der of m divided by n. Verify that this algorithm works for the
examples shown in the first paragraph. Then write this function and
test it out.

Explanation / Answer

#include <iostream>
using namespace std;

int main()
{
   //PROTOTYPES
   int euclid(int m, int n);

   //LOCAL DECLARATIONS
   int m = 0, n = 0;

   //PROCEDURES
   while (m < 1)
   {
      cout << "Enter first number: ";
      cin >> m;
      if (m < 1)
         cout << "Invalid number. "
              << "Number must be positive" << endl;
   }
   while (n < 1)
   {
      cout << "Enter second number: ";
      cin >> n;
      if (n < 1)
         cout << "Invalid number. "
              << "Number must be positive" << endl;
   }
   cout << " Greatest common divisor of "
        << m << " and " << n << " is "
        << euclid(m, n) << endl;;


   cout << endl;
   cin.sync();
   cin.get();
   return 0;
}

//---------------------------------------------------------
// FUNCTION DEFINITIONS
//---------------------------------------------------------
int euclid(int m, int n)
{
   if (m < n)
      return euclid(n, m);
   else if (m % n == 0)
      return n;
   else
      return euclid(n, m % n);
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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