C++ How To Find the Greatest Common Divisor (GCD)
Find the Greatest Common Divisor (GCD)
The greatest common divisor (GCD) is the largest number that divides two numbers without a remainder. Find it with the Euclidean algorithm:
Example
int a = 36;
int b = 60;
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
cout << "GCD: " << a;Explanation:
In each step, b becomes the remainder of a / b, and a becomes the old b.
When the remainder is 0, a holds the GCD. 36 and 60 can both be divided by 12.
