最大公约数
最大公约数与最小公倍数
G.C.D: greatest common divisor, 最大公约数
L.C.M: least common multiple, 最小公倍数
对于 $x$, $y$ 有公式:
x \times y = gcd \times lcm
辗转相除法
辗转相除法, 又名欧几里德算法 (Euclidean algorithm) 乃求两个正整数之最大公因子的算法. 它是已知最古老的算法, 其可追溯至公元前 300 年前.
辗转相除法是求最大公约数的一种方法. 它的具体做法是: 用较小数除较大数, 再用出现的余数 (第一余数) 去除除数, 再用出现的余数 (第二余数) 去除第一余数, 如此