Back to Math Tools
GCD/LCM Calculator
Calculate greatest common divisor (GCD) and least common multiple (LCM) of two or more integers with prime factorization
Number Input
Quick Examples
Calculation Results
Enter at least two integers and click 'Calculate GCD/LCM' to start
Algorithm Explanation
Euclidean Algorithm
Classical algorithm for calculating GCD of two numbers, based on the principle: gcd(a, b) = gcd(b, a mod b). High efficiency with time complexity O(log min(a, b)).
Extend to Multiple Numbers
GCD of multiple numbers can be calculated by successive pairwise GCD: gcd(a, b, c) = gcd(gcd(a, b), c). Same for LCM: lcm(a, b, c) = lcm(lcm(a, b), c).
GCD and LCM Relationship
For two positive integers a and b: gcd(a, b) × lcm(a, b) = a × b. This relationship can be used to verify calculation correctness.