In mathematics, the greatest common divisor(gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder(amount left over after peforming a division).

*Example:*

gcd(8, 12) = 4

The greatest common divisor is also known as the greatest common factor(gcf), highest common factor(hcf), greatest common measure(gcm) or highest common divisor.

I will present you the algorithm for this below:

#include <iostream>

using namespace std;

int gcd(int a, int b) // greatest common divisor of two numbers using repeated falls

{

while(a != b) // while this two numbers are different

{

if(a > b)

a = a - b;

else

b = b - a;

}

return a; // greatest common divisor will be saved in first number

}

int main()

{

cout<<gcd(8, 12);

cout<<endl;

return 0;

}

**There are 5 more methods to find gcd, more optimized. One of them complexity is best. Check bellow buttons(PayPal)!!!**

## No comments:

Write comments