GCD / LCM
Learn GCD / LCM (Foundations, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
GCD and LCM The GCD (greatest common divisor) of two numbers is the largest number that divides both. Euclid's algorithm finds it by repeating gcd(a, b) = gcd(b, a % b) until b becomes 0. The LCM (least common multiple) follows from lcm(a, b) = a / gcd(a, b) * b . Euclid's algorithm runs in O(log min(a, b)) .