C++ Program to Find the GCD of Two Numbers

What is GCD (Greatest Common Divisor)?

As the name explains, the GCD (Greatest Common Divisor) of two numbers is the greatest positive integer that divides the numbers without leaving any remainder.
GCD is also known as HCF (Highest Common Factor).

As we have studied in school, We can find the GCD of two numbers by multiplying their common prime factors.

In this example, we will find GCD of 140 & 240,

Prime factors of 140: 2, 2, 5, 7

Prime factors of 270: 2, 3, 3, 3, 5,

Common Prime factors of 140 & 270: 2, 5

GCD(140,270) = Product of the common factors = 2 * 5 = 10

Algorithms to Find the GCD of Two Numbers

There are many algorithms for finding the GCD of two numbers, but the underlying principle in all of them is the same, i.e., the GCD of two numbers is equal to the product of their common factors. We can also use the inbuilt GCD function C++, discussed in the 4th approach.

Approach 1 - Prime Factorization method

In this algorithm, we will find the common factors of both numbers and then return the product of the common factors as the GCD of the two numbers.

Steps of the algorithm:

1. Create a function gcd(), and pass two numbers to it.
2. Create a function getFactors(), which returns a vector containing all the prime factors of the number passed to it.
3. Create a function isPrime(), which checks whether a number is a prime or not.
4. Inside the getFactors() function, use the isPrime() function to check whether the factors are prime numbers or not, then return the vector.
5. Inside the gcd() function, check if a or b is equal to 0, if yes, return $a+b$.
6. After that, initialize a variable GCD=1 inside the gcd() function and multiply it by the factors common in both vectors.
7. Return the GCD.

Implementation:

Output:

In the above example, we find the GCD of two user input numbers $75$ and $50$ using the Prime Factorization method. At first, we store all the prime factors of both numbers in different vectors; after that, we find the intersection of both vectors and multiply the common factors by the GCD of those two numbers. Lastly, we will return and then print the GCD.

Time Complexity: $O(max(a, b))$
The time complexity of the getFactors() function is O(max(a, b) as its while loop is amortized, whereas the time complexity of gcd() is (max(a, b)).
The asymptotic time complexity will be O(max(a, b)).

Approach 2 - Euclidean Algorithm

The Euclidean Algorithm is an efficient method for calculating the GCD of two numbers, named after the ancient Greek mathematician Euclid. This algorithm was first described in his book "Elements".

The Euclidean Algorithm states that $GCD(a,b) = GCD(a, b-a)$.

Proof of the Euclidean Algorithm:
Suppose we have 3 integers: a, b, and c, such that $a-b = c$.

The GCD(a,b) evenly divides $a$ and $b$ by definition.
As a result, $a$ and $b$ are multiples of GCD(a,b), i.e., $a = GCD(a,b)*x$, for some positive integer $x$ and $b = GCD(a,b)*y$, for some positive integer $y$.

Putting the values of $a$ and $b$ in $a - b = c$ :
$\implies c = x*GCD(a,b) - y*GCD(a,b)$.
$\implies c = (x-y)*GCD(a,b)$

An illustration of this is in the figure below:

The $GCD(b,c)$ evenly divides $b$ and $c$ by definition.
As a result, $b$ and $c$ are multiples of $GCD(b,c)$, i.e., $b = GCD(b,c)*p$, for some positive integer $p$ and $c = GCD(b,c)*q$, for some positive integer $q$.

Putting the values of $b$ and $c$ in $a - b = c$ :
$\implies a - p*GCD(b,c) = q*GCD(b,c)$.
$\implies a = (p+q)*GCD(b,c)$

An illustration of this is in the figure below:

The $GCD(a,b)$ divides both $b$ and $c$ and $GCD(b,c)$ divides both $a$ and $b$.
$\implies GCD(a,b) \leq GCD(b,c)$ as $GCD(b,c)$ is the "GREATEST" common divisor of $b$ and $c$.
$\implies GCD(b,c) \leq GCD(a,b)$ as $GCD(a,b)$ is the "GREATEST" common divisor of $a$ and $b$.

An illustration of this is in the figure below:

Therefore, $GCD(a,b) = GCD(b,c)$, where $c = a - b$,
$\implies GCD(a,b) = GCD(b,a-b)$.

Steps of the algorithm:

1. Create a function $gcd()$, and pass two numbers to it.
2. If $a$ or $b$ is $0$, return $a+b$.
3. If $a == b$, return $a$.
4. If $a > b$, return $gcd(a-b, a)$.
5. If none of those conditions satisfy, return $gcd(a-b, a)$.

Implementation:

Output:

In the above example, we are computing the GCD of two user input numbers $88$ and $100$ using Euclid's Algorithm.

Time Complexity: $O(a+b)$
In this algorithm, the number of steps is linear, e.g., $GCD(x, 1)$, in which we will subtract $1$ from $x$ in each recursion so that the time complexity will be $O(a+b)$.

Approach 3 - Optimized Euclidean Algorithm (Using the modulo operator)

As we have just learned about the Euclidean Algorithm in the previous section, We will now learn about its optimized version, i.e., using the modulo operator.

The Optimized Euclidean Alogrithm states that if, $a = b*q + r$ and $b\neq0$, where $q$ is the quotient and $r$ is the remainder, then $GCD(a, b) = GCD(b, r)$.

Proof of the algorithm:
We have just proved that $GCD(a,b) = GCD(b, a-b)$, but what if we repeatedly apply this rule to itself? Let's set what happens.

$GCD(a,b) = GCD(b, a-b)$ $\implies GCD(b, a-b) = GCD(b, a-2*b) = GCD(b, a-3*b)$ and so on...

Therefore, $GCD(a,b) = GCD(b, a-q*b)$, where $a-q*b = r$,
$\implies GCD(a,b) = GCD(b, r)$

Steps of the algorithm

1. Create a function $gcd()$, and pass two numbers to it.
2. If $b=0$, return $a$.
3. Otherwise, return $gcd(b, a\%b)$.

Implementation:

Output:

In the above example, we are computing the GCD of two user input numbers $54$ and $0$ using the Optimized Euclid's Algorithm.

Time Complexity: O(log max(a,b))
In this algorithm, we are recursively calling $GCD(b,a\%b)$, reducing the second parameter by $a\%b$ in each function call, so the time complexity will be $O(log\;max(a,b))$.

Approach 4 - Using __gcd(a,b) function.

We can also use the inbuilt GCD function C++ __gcd() included in the <algorithm> header file to find the GCD of two numbers.

Implementation:

Output:

In the above example, we are computing the GCD of two user input numbers, 54 and 22, using the GCD function C++.