The GCD (Greatest Common Divisor) and LCM (Least Common Multiple) of two integers in C are most efficiently found using Euclid’s algorithm. The algorithm repeatedly replaces the larger number with the remainder of dividing the two numbers until the remainder is zero — what remains is the GCD. The LCM then follows from the identity …