In mathematics, the greatest common divisor (GCD) of two or more integers, is the largest positive integer that divides each of the integers.

For example,

Divisors of 8: 1, 2, 4, 8

Divisors of 16: 1, 2, 4, 8, 16

Divisors of 12: 1, 2, 3, 4, 6, 12

The GCD of 8, 16 and 12 is 4 because it is both a common divisor to each of them and the greatest of their common divisors. Sometimes, it is also called the highest common factor (HCF).

In this lesson, we will start with the most obvious solution and then tweak it till we get an efficient one. So let’s start!

Finding the GCD of two numbers

We need to determine the biggest number that divides the two numbers. We can make a function (let’s call it gcd()) that takes two integers n1, and n2 and determines the greatest number, which divides both numbers.

Implementations of GCD

Let’s discuss the different ways of implementing the GCD function. As we move forward, we’ll try to come up with the least complex implementation of this complex problem.

1. The naive version

Say the two numbers are 20 and 40. The most straightforward approach that comes to mind is that we keep dividing both numbers by 1 up to one of the numbers (either 40 or 20) to see which greatest number divides both numbers, and then return that number.

So our function might look like this:

Press + to interact
int gcd1(int n1, int n2)
{ 
   int greatestDivisor = 1; 
   //initialised with 1 because 1 is always a common divisor
     
   for (int d = 2; d <= n1; d++)
   {
      if(n1 % d == 0 && n2 % d == 0)
      {
         greatestDivisor = d; 
            // Save d, note the previous value will be replaced with the greater value
      }  
   }    
   return greatestDivisor; // This returns the largest number that divided both n1 and n2
}

Though the above function would work just fine, we could modify it to make it a bit more efficient.

2. Division till the smaller of the two numbers

Because the greatest divisor cannot be greater than the smaller of the two numbers, we can divide the two numbers by 1 up to the smaller number of the two. Assuming the two numbers n1 and n2 are 20 and 40, the GCD cannot be greater than 20 (the smaller of the two numbers).

Our idea is to first find the smaller of the two numbers n1 and n2. Then we can easily argue that the GCD has to be one of the numbers between 1 and s (the smaller number).

So we can make a new function called smaller() that returns the smaller number of the two like this:

Press + to interact
int smaller(int n1, int n2)
  {
    if (n1 < n2)
       return n1;
    else
       return n2; 
  }

So the condition in the for loop of our gcd() function should now become d <= s; where s is the smaller number:

Press + to interact
int gcd2(int n1, int n2)
{ 
   int greatestDivisor = 1;
   int s = smaller(n1, n2); 
 
   for (int d = 1; d <= s; d++)
   {
      if(n1 % d == 0 && n2 % d == 0)
      {
         greatestDivisor = d; 
      }  
   }    
   return greatestDivisor;
}

Now we iterate from 1 to s and update if any number between the range divides both n1 and n2. The last number that divides both n1 and n2 will be our GCD.

3. Division by the smaller number backward toward 1

Since we’re looking for the greatest divisor, instead of checking for the divisors from 1 to s, why don’t we check the divisors from s to 1?

We can iterate from s to 1 and return the first number that divides both n1 and n2. This way, we can find the greatest divisor quickly.

So we could write it like this:

Press + to interact
int gcd3(int n1, int n2)
{      
   int s = smaller(n1, n2); 
   for (int d = s; d >= 1; d--)
   // initialising d with either number
   {
      if(n1 % d == 0 && n2 % d == 0)
      {
         return d; 
           // returns the first divisor that divides both numbers
      }  
   }    
   return 1;  // this is to avoid warning as this instruction will never execute
}

In the above function, in the for statement, we have the following

   for (int d = s; d >= 1; d--)

We initialized d with the smaller number and decremented it till d <= 1. This way, the first greatest divisor is returned quickly without having to go through multiple iterations.

4. Euclid’s division

Before we see our least complex solution of the GCD problem, let’s first talk about the famous mathematician Euclid’s strategy for finding the step-by-step solution for the GCD, (known as the Euclidean algorithm). This algorithm has made it possible to compute the GCD of very, very large numbers in just a few steps! In fact, if we did not have this algorithm, the current world of cryptography wouldn’t exist (because GCD is one of the foundational tools to compute several important quantities like inverses in finite fields).

Euclid’s algorithm includes the following elegant steps:

  • Given the two numbers, we simply divide one number with the other and find the remainder.
  • The remainder becomes the divisor, and the divisor becomes the dividend, so we carry out the repeated division till the remainder is zero.
  • The divisor which gives zero as the remainder is our GCD.
Press + to interact
int gcdEuclid(int n1, int n2)
{    
   while (n1 % n2 != 0)
   // n2 does not completely divide n1
   {
      int rem = n1 % n2;
      n1 = n2; 
      n2 = rem; 
   }    
   return n2;
}

In the above version, we update n1 with the value of n2. The n2 becomes equal to the remainder. So, in short, it’s like a long division where the remainder becomes the divisor, and the divisor becomes the dividend. As long as the remainder is not zero, we keep dividing.

Press + to interact
Euclid's division
Euclid's division

Comparing all the GCD implementation versions

Let’s test all four GCD implementation versions in the playground below to see what we meant by gcdEuclid() being more efficient than the other three implementations.

Instruction: Test all four GCD implementations on the large numbers. You may change the numbers in the code below to see how they affect the execution time of the respective implementation version.

🕵🏻‍♂️ Run the code directly (n_ot step by step_) by removing the breakpoint first and clicking the start button ( ). Also, don’t worry about the function implementations, we’ve already included them, you just have to click the Run button.

#include <iostream>
using namespace std;
// We've changed the data type to long long because we're using larger numbers 
long long gcdEuclid(long long n1, long long n2);
long long gcd1(long long n1, long long n2);
long long smaller(long long n1, long long n2);
long long gcd2(long long n1, long long n2);
long long gcd3(long long n1, long long n2);

int main()
{
   // Testing all the gcd implementation versions below on the following numbers:
   long int start = time(0);
   cout<< gcdEuclid(11927654321, 1197654321)<<endl;
   cout << "EuclidGCD took "<<time(0)-start << " seconds.\n";
 
   start = time(0);
   cout<< gcd3(11927654321, 1197654321)<<endl;
   cout << "Naive3GCD took "<<time(0)-start << " seconds.\n";

   start = time(0);
   cout<< gcd2(11927654321, 1197654321)<<endl;
   cout << "Naive2GCD took "<<time(0)-start << " seconds,\n";

   start = time(0);
   cout<< gcd1(1927654321, 197654321)<<endl;
   cout << "Naive1GCD took "<<time(0)-start << " seconds.\n";
   
}
Exercise: the gcdEuclid() function

We used the gcdEuclid() function to calculate the GCD of two numbers. What if we had to calculate the GCD of 50 numbers?

We can easily use the code above to do that. Let’s see how in the program below

GCD of k numbers

Now let us calculate the GCD of k numbers.

Observe that if we would like to find the GCD of, let’s say, 3 numbers, we can calculate it by first calculating the GCD of two numbers and storing it in a variable. Let’s say we can calculate it by first calculating the GCD of two numbers and storing it in a variable, let’s say g,then to compute the GCD of the three numbers we compute the GCD of g, and the third number.

Similarly, for finding the GCD of 4 numbers we can proceed with storing the last answer in g again and computing the GCD of g and the fourth number and so on.

Here is what the solution looks like.

#include <iostream>
using namespace std;

int gcd(int n1,int n2);

int main()
{
    int k = 0;
    // In this scenario the value of k is 5 
    cout << "The k numbers you want to calculate the GCD of: ";
    cin >> k;
    int n1, nextNum, g;
    cout << "First number: ";
    cin >> n1;
    cout << "Next number: ";
    cin >> nextNum;

    g = gcd(n1, nextNum);
    
    cout << "Next number: ";
    cin >> nextNum;
    g = gcd(g, nextNum);
    cout << "Next number: ";
    cin >> nextNum;
    g = gcd(g, nextNum);
    cout << "Next number: ";
    cin>> nextNum;
    g = gcd(g, nextNum);
    
    cout << g << " is the greatest common divisor." << endl;
}

int gcd(int n1, int n2)
{    
   while (n1 % n2 != 0)
   {
      int rem = n1 % n2;
      n1 = n2; 
      n2 = rem; 
   }    
   return n2;
}
Calculating the greatest common divisor of multiple numbers

e can see from the code above that the highlighted part (lines 20–28) can be rewritten with the help of a loop. That is, we store the GCD of the first two numbers outside the loop. Then, inside the loop, we start i from 3, since we are taking the third number as the input, and go up to n. We calculate the GCD of g and the ith number and store it back in g. Here, g is acting as an accumulator for the answer of the GCD up to the ith numbers

So we have the following implementation:

#include <iostream>
using namespace std;

int gcd(int n1,int n2);

int main()
{
    int n=0;
    cout << "The k numbers you want to calculate the GCD of: ";
    cin >> n;
    int n1, nextNum, g;
    cout << "First number: ";
    cin >> n1;
    cout << "Next number: ";
    cin >> nextNum;
    g = gcd (n1, nextNum);

    for(int i=3;i<=n;i++)
    {
        cout << "Next Number : ";
        cin >> nextNum;
        g = gcd (g,nextNum);
    }
    cout << g << " is the GCD." << endl;
}

int gcd(int n1, int n2)
{    
   while (n1 % n2 != 0)
   {
      int rem = n1 % n2;
      n1 = n2; 
      n2 = rem; 
   }    
   return n2;
}
Calculating the greatest common divisor of k numbers

How good is Euclid’s GCD?

Although it is beyond the scope of this course, we think it is vital that when we say a certain approach is more efficient than the other, we have a sound understanding of why and how it is so.

If we analyze carefully, we can deduce that the naive implementation runs the loop with maximum iterations equaling the larger of the two numbers (the second and third implementations, in the worst-case, run as many times as the smaller of the two numbers).

If we were to take a discrete mathematics course, we would easily understand that the Euclidean GCD executes in such a way that in each iteration, either n1n_1 or n2n_2 becomes less than or equal to its half (you may look at the illustration of Euclid’s division above). Hence, the number of iterations becomes either log(n1)log (n_1) or log(n2)log(n_2).

Now let us see the difference between the two approaches.

Suppose that n1n_1 and n2n_2 are very large numbers say around 1000 digits long (which is quite normal when we are working in cryptography, in which our entire data sent over the network gets converted/encrypted into big numbers).

So we have n1≈101000n_1\approx 10^{1000} and n2≈101000n_2\approx 10^{1000}.

So the naive approach will execute approximately 10100010^{1000} iterations whereas Euclidean GCD will execute only log(101000)=1000×log210=3321.928log (10^{1000}) = 1000 \times log_2 10 = 3321.928 (this means approximately 3322 steps or even less). That is a huge difference!

Naive Implementation

Imagine now that we are running on a machine that is very fast and executes one iteration of a loop in just 1 nanosecond. Then the naive machine algorithm will execute the GCD program in

=101000109seconds=10991seconds=\frac{10^{1000}}{10^9} seconds = 10^{991} seconds

WWe can convert it into minutes (by dividing it by 60) and into hours (if we divide it further by 60) and into days (by dividing it further by 24) and into years (by dividing it further by 365) and into centuries (by dividing it further by 100).

Hence, it will become the following:

=1099160×60×24×365×1000centuries=\frac{10^{991}}{60 \times 60 \times 24 \times 365 \times 1000} centuries

=1099131536000000centuries= \frac{10^{991}}{31536000000} centuries

≈10980centuries\approx 10^{980} centuries

Euclidean GCD

In comparison, the Euclidean approach will only take log⁡2101000=3322\log_2{10^{1000}} = 3322 iterations at most.

Hence our program will take this many seconds:

3322109=3.322 micro seconds\frac{3322}{10^9} = 3.322 \space micro \space seconds

This is a huge difference, where one algorithm is taking many centuries and the other only a few microseconds. No wonder we rightfully call the Euclidean algorithm an elegant algorithm.

We hope that you learned how important it is for a good computer scientist to come up with an efficient implementation. Finding efficient algorithms and analyzing our algorithm’s efficiency are profound skills and are important in practical applications.