How to find the greatest common divisor between two integers? We may encounter this problem frequently in interviews or other occasions.
An efficient metho to find gcd is the Euclidean algorithm, which uses the division algorithm in combination with the observation that the gcd of two numbers also divides their difference: divide 48 by 18 to get a quotient of 2 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd. Formally, it could be written as
gcd(a,0) = a
gcd(a,b) = gcd(b,a mod b)
The code can be shown below;