返回上级
GCD/LCM 计算器
计算 greatest common divisor (GCD) and least common multiple (LCM) of two or more integers with 质因数分解
数字输入
快速示例
Calculation 结果
Enter at least two integers and click '计算 GCD/LCM' to 开始
算法说明
欧几里得算法
Classical algorithm for calculating GCD of two 个数字, based on the principle: gcd(a, b) = gcd(b, a mod b). 高 效率 with time complexity O(log min(a, b)).
扩展到多个数字
GCD of multiple 个数字 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和LCM的关系
For two positive integers a and b: gcd(a, b) × lcm(a, b) = a × b. This relationship can be used to verify calculation correctness.