Greatest common factor calculator
Greatest common factor problem
Given two integers A less than B. Write code to find the greatest common divisor between A and B commonly known as GCD.
What is a greatest common factor
GCD(A, B) is the largest positive integer that divides A and B without a remainder. We can loop starting at 2 ending at A and whenever we find a divisor for both A and B we update our result. At the end of the loop we will have GCD already computed.
How to find the greatest common factor
Here is a sample C++ code to do that
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
void main() { //Example numbers int A = 51; int B = 85; //By default GCD = 1 int gcd = 1; //Check all numbers from 2 to A (smaller one) for (int i = 2; i <= A; i++) { //If the current number divides both of them //update GCD if (A%i == 0 && B%i == 0) { gcd = i; } } //At the end we will have GCD computed cout << "GCD = " << gcd << endl; } |
Solution
The first solution is inefficient in case of large numbers. There is a very efficient approach to solving this problem known as the Euclidean algorithm. The Euclidean algorithm is based on the fact that the GCD of two numbers does not change if the smaller number is subtracted from the larger number. Since the larger number is reduced repeating the same step produces smaller numbers until one of them is zero. In that case the GCD is the remaining nonzero number. To illustrate that look at the following example:
|
1 |
GCD(51, 85) = GCD(34, 51) = GCD(17, 34) = GCD(17, 17) = GCD(0, 17) = 17 |
Code
Here is an iterative implementation in C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
int GCD(int A, int B) { if (A == 0) { return B; } while(B != 0) { if (A > B) { A = A - B; } else { B = B - A; } } return A; } |
Here is the recursive flavor of the Euclidean algorithm
|
1 2 3 4 5 6 7 8 9 10 11 |
int GCD(int A, int B) { if (B == 0) { return A; } else { return GCD(B, A%B); } } |
If you have questions or comments, please use the comments section below. Thanks for reading.
About Author
Mohammed Abualrob
Software Engineer @ Cisco