C++ program to calculate the greatest common factor

The highest common factor or greatest common divisor is a factor that can divide two or more values ​​simultaneously without producing any remainder. In this article, we will discuss several ways to perform HCF/GCD of two numbers in C.

This is just a mathematical solution, there are several algorithms to find the greatest common divisor. Euclidean method is a common way to find the greatest common divisor. We will use the same algorithm in iterative and recursive mode.

Use iteration method

Euclidean iterative solution to find the greatest common divisor is shown in the algorithm section.

algorithm

• Take two numbers a and b as input.
• If a is equal to 0, return b.
• If b is 0, return a.
• When a and b are not the same, perform the operation.
  • If a > b, then a := a – b.
  • Otherwise b := b - a.
• End the loop.
• Return the greatest common factor as variable a.

Example

#include <iostream>
using namespace std;

int solve( int x, int y) {
   if (x == 0)
      return y;
   else if (y == 0)
      return x;
   while (x != y) {
      if (x > y)
         x = x - y;
      else
         y = y - x;
   }
   return x;
}

int main( int argc, char* argv[] ) {
   cout << "HCF of two numbers 12 and 72 is: " << solve(12, 72) << endl;
   cout << "HCF of two numbers 18 and 13 is: " << solve(18, 13) <<   endl;
   cout << "HCF of two numbers 117 and 96 is: " << solve(117, 96) << endl;
   cout << "HCF of two numbers 85 and 15 is: " << solve(85, 15) << endl;
}

Output

HCF of two numbers 12 and 72 is: 12
HCF of two numbers 18 and 13 is: 1
HCF of two numbers 117 and 96 is: 3
HCF of two numbers 85 and 15 is: 5

Use iteration method

The same Euclidean method can be implemented using recursive methods. Below we describe the definition of a recursive method, the algorithm shown below.

algorithm

• Define a function called HCF that accepts two numbers a and b.
• If a is 0, return b
• Otherwise return HCF( b mod a, a)

Example

#include <iostream>
using namespace std;

int solve( int x, int y) {
   if (x == 0)
      return y;
   return solve( y % x, x );
}

int main( int argc, char* argv[] ) {
   cout << "HCF of two numbers 12 and 72 is: " << solve(12, 72) << endl;
   cout << "HCF of two numbers 18 and 13 is: " << solve(18, 13) << endl;
   cout << "HCF of two numbers 117 and 96 is: " << solve(117, 96) << endl;
   cout << "HCF of two numbers 85 and 15 is: " << solve(85, 15) << endl;
}

Output

HCF of two numbers 12 and 72 is: 12
HCF of two numbers 18 and 13 is: 1
HCF of two numbers 117 and 96 is: 3
HCF of two numbers 85 and 15 is: 5

in conclusion

Finding the greatest common factor or greatest common divisor is very useful when solving different mathematical problems. It can be calculated using the Euclidean method. This method can be applied iteratively or recursively. Here we show two methods. On the other hand, we can calculate GCD/HCF via the least common multiple (LCM). The GCD and LCM of two numbers are the same as the product of the two numbers. So, according to this principle, if we know the LCM and product of these two numbers, we can easily calculate the GCD.

The above is the detailed content of C++ program to calculate the greatest common factor. For more information, please follow other related articles on the PHP Chinese website!