Euclid\'s method for finding the greatest common divisor (GCD) of two positive i

Question

Euclid's method for finding the greatest common divisor (GCD) of two positive integers consists of the following steps:
Step 1: Divide the larger number by the smaller and retain the remainder.
Step 2: Divide the smaller number by the reminder, again retaining the remainder.
Step 3: Continue dividing the previous remainder by the current remainder until the remainder is zero, at which point the last non-zero remainder is the GCD.
For example, if the two positive integers are 84 and 49, you have the following:
Step 1: 84/49 yields a remainder of 35.
Step 2: 49/35 yields a remainder of 14.
Step 3: 35/14 yields a remainder of 7.
Step 4: 14/7 yields a remainder of 0.
Therefore, the last non-zero remainder, which is seven, is the GCD of 84 and 49.
Using Euclid's algorithm, write a function in C++ that determines and returns the GCD of two integer arguments.

Explanation / Answer

#include <iostream>
using namespace std;

int EuclidGcd(int, int);

int main()
{
   int a = 84;
   int b = 49;

   cout << "Greatest common divisor of "
        << a << " and " << b << " is "
        << EuclidGcd(a, b) << endl;

   cin.get();
   return 0;
}

//---------------------------------------------------------
int EuclidGcd(int a, int b)
{
   if (a <= 0 || b <= 0)
      return 0;
   if (a > b)
      if (a % b)
         return EuclidGcd(b, a % b);
      else
         return b;
   else
      if (b % a)
         return EuclidGcd(a, b % a);
      else
         return a;
}

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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