GCD
The greatest common divisor (GCD) of two numbers is the largest number that divides both numbers. Several algorithms can efficiently compute the GCD.
Java example (Euclidean algorithm):


C++ example (Euclidean algorithm):


Python example (Euclidean algorithm):


The GCD can be computed efficiently in O(log(min(a,b))) time via the Euclidean algorithm, which recursively computes the GCD of remainders.
Other methods include binary GCD and using prime factorization. GCD is useful for simplifying fractions and various mathematical operations.
The Greatest Common Divisor (GCD) is the largest positive integer that divides two or more integers without leaving a remainder. For example, the GCD of 8 and 12 is 4. The GCD of two numbers a
and b
can be found using Euclid’s algorithm. The algorithm is based on the principle that the GCD of a
and b
is the same as the GCD of a
and a % b
.
Example Code
Java


C++


Python


In these examples, the function gcd
takes two integers a
and b
as input. It uses recursion and Euclid’s algorithm to find the GCD. If b
is 0, it returns a
. Otherwise, it calls itself with b
and a % b
.