Euclid’s Division Lemma Using C++

Filed Under: C++
Euclid's Division Lemma Using C

In today’s article, we will learn Euclid’s division lemma using C++. If you’re a competitive programmer, or even if you are not, this algorithm is a must to learn. It will always help you throughout your programming journey. What makes this algorithm so special is its very efficient time complexity. Let’s get started. I can promise that you won’t ever regret learning this theorem.

What’s Is Euclid’s Division Lemma?

This amazing algorithm is a way to find the HCF(Highest Common Factor) of two numbers. It states that for every pair ‘a’ and ‘b’, there exists the following relation.

a = bq + r, where 0 <= r < b

To find the HCF, keep dividing a with b until the remainder is zero. With every division, the new ‘a’ will become ‘b’ and the remainder will become new ‘b’.

Some examples to get an intuition regarding the algorithm is,

Let's start with a simpler one
HCF of 20 and 15
1st iteration:
20 % 15 = 5
New 'a' = 15 and new 'b' = 5

2nd iteration:
15 % 5 = 0
New 'a' = 5 and new 'b' = 0

3rd iteration:
a = 5 and b = 0
Since b == 0, we will stop here and return a = 5 as the answer

Another one,
HCF of 90 and 27
1st iteration:
90 % 27 = 9
New 'a' = 27 and new 'b' = 9

2nd iteration:
27 % 9 = 0
New 'a' = 9 and new 'b' = 0

3rd iteration:
b == 0, hence, we return 'a' = 9 from here

Pseudocode

As you can notice the general flow of control of the algorithm. We will go through the following steps while writing the algorithm

  • The function will be of the form: gcd(int a, int b)
  • Base case: This is a recursive algorithm and thus we must define a base case.
    • if(b == 0)
      • return a
  • Recursive case
    • return gcd(b, a % b)

That’s it, we’ve developed the algorithm. Yes, it’s only a two steps algorithm. Now, let’s quickly write the underlying code

Algorithm for Euclid’s Division Lemma

Let’s look at the algorithm for solving the Euclid’s Division Lemma.

// function to calculate the
// greatest common divisor
int gcd(int a, int b)
{
        // to make the algorithm more
        // intuitive, let's print
        // some more information
        // The following information
        // will help you understand
        // the flow of data across each
        // function call
        cout << "a: " << a << " and b: " << b << endl;

        // base case
        if(b == 0)
        {
                return a;
        }

        // recursive case
        // new_a = b;
        // b = a % b;
        return gcd(b, a % b);

Euclid’s Division Lemma Using C++ Progam

Let’s now work on implementing the above algorithm for Euclid’s Division Lemma in C++.

#include <iostream>

using namespace std;

// function to calculate the
// greatest common divisor
int gcd(int a, int b)
{
	// to make the algorithm more
	// intuitive, let's print
	// some more information
	// The following information
	// will help you understand
	// the flow of data across each
	// function call
	cout << "a: " << a << " and b: " << b << endl;
	
	// base case
	if(b == 0)
	{
		cout << "The gcd of the two numbers is: " << endl;
		return a;
	}

	// recursive case
	// new_a = b;
	// b = a % b;
	return gcd(b, a % b);
}

int main()
{
	int a, b;

	cout << "Enter two numbers" << endl;
	cin >> a >> b;

	cout << gcd(a, b) << endl;

	return 0;
}
Algorithm And Driver Code
Algorithm And Driver Code

Output

GCD Output
GCD Output

Space And Time Complexity Analysis

The space complexity of the current algorithm is constant, this is because we are not using any extra space while computing.

The time complexity of the algorithm is log(min(a, b)). This explains why it is so fast in practice.

Conclusion

In this article, we learned a very interesting algorithm – Euclid’s division lemma using C++. We started by going through the lemma, then we went through some easy examples. Then we moved toward the concept and pseudocode. In the end, we developed the algorithm and a driver program to test the working of the algorithm in different scenarios. That’s all for today, thanks for reading.

Further Readings

To learn more about C++ algorithms and data structures, you go through the following articles.

https://www.journaldev.com/58739/tiling-problem-dynamic-programming-cpp

https://www.journaldev.com/60947/rotate-images-using-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content