Introduction
The Euclidean algorithm, also known as Euclid's algorithm, is an effective way to determine the greatest common divisor (GCD), or the biggest number that divides two integers (numbers) evenly without leaving a remainder. The Greek mathematician Euclid, who first described it in his Elements, gave it his name.
In this article, we will discuss the euclidean algorithm in detail. So, Stay till the end!
Euclidean Algorithm
The Euclidean algorithm is based on the premise that if the larger number is swapped out for its difference with the smaller number, the greatest common divisor of the two numbers remains the same. For instance, the GCD of 252 and 105 is 21 (because 252 = 21 x 12 and 105 = 21x5), and 21 is also the GCD of 105 and 252-105 = 147. Repeating this method results in gradually smaller pairs of numbers until the two numbers are equal since this replacement reduce the larger of the two numbers. They are the GCD of the initial two numbers when that happens. The GCD can be written as the linear combination of the two original numbers, that is, the sum of the two integers, each multiplied by an integer (for instance, 21 = 5x105 + (-2) x 252), by reversing the steps or applying the extended Euclidean method.
Algorithm
- GCD remains the same if we lower a larger integer by subtracting a smaller one. Therefore, if we repeatedly deduct the larger of two, we arrive at GCD.
- Now, if we divide the smaller number rather of subtracting it, the process halts when we reach the final result of 0.
Code
#include <bits/stdc++.h>
using namespace std;
int gcd(int p, int q)
{
if (p == 0)
return q;
return gcd(q % p, p);
}
int main()
{
int p = 256, q = 12;
// Function call
cout << "GCD(" << p << "," << q << "`) = " << gcd(p, q) << endl;
p = 42, q = 7;
cout << "GCD(" << p << "," << q << ") = " << gcd(p, q) << endl;
p = 35, q = 7;
cout << "GCD(" << p << "," << q << ") = " << gcd(p, q) << endl;
return 0;
}
Output
Time Complexity: O(Log min(p, q))
Auxiliary Space: O(Log (min(p, q))
Example
- Find the GCD of 192 and 78
- A=192, B=78
- A ≠0
- B ≠0
- Use long division to find that 192/78 = 2 with a remainder of 36. We can write this as:
- 192 = 78 * 2 + 36
2. Find GCD(78,36), since GCD(192,78)=GCD(78,36)
- A=78, B=36
- A ≠0
- B ≠0
- Use long division to find that 78/36 = 2 with a remainder of 6. We can write this as:
- 78 = 36 * 2 + 6
3. Find GCD(36,6), since GCD(78,36)=GCD(36,6)
- A=36, B=6
- A ≠0
- B ≠0
- Use long division to find that 36/6 = 6 with a remainder of 0. We can write this as:
- 36 = 6 * 6 + 0
4. Find GCD(6,0), since GCD(36,6)=GCD(6,0)
- A=6, B=0
- A ≠0
- B =0, GCD(6,0)=6
So we have shown:
GCD(192,78) = GCD(78,36) = GCD(36,6) = GCD(6,0) = 6
GCD(192,78) = 6