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).
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>There are 5 more methods to find gcd, more optimized. One of them complexity is best. Check bellow buttons(PayPal)!!!
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;
b = b - a;
return a; // greatest common divisor will be saved in first number