本文共 482 字，大约阅读时间需要 1 分钟。
辗转相除法，又被称为欧几里德（Euclidean）算法， 是求最大公约数的算法。
当然也可以求最小公倍数。算法描述
两个数a，b的最大公约数记为GCD(a,b)。a，b的最大公约数是两个数的公共素因子的乘积。如462可以分解成2 × 3 × 7 × 11；1071可以分解成3 × 3 × 7 × 17。462和1071的最大公约数等于它们共有的素因数的乘积3 × 7 = 21。如果两数没有公共的素因数，那么它们的最大公约数是1，也即这两个数互素，即GCD(a,b)=1。另g=GCD(a,b)，则a=mg, b=ng，其中m，n均为正整数。由上述分析可知，m，n互素。因为m，n没有公共素因子，GCD(m,n)=1。
辗转相除法是一种递归算法。算法实现：
递归版本：private static int gac(int a, int b) { if(a 循环版本：
private static int gac(int a, int b) { if(a 2个数a,b;已知最大公约数为n；
最小公倍数=a*(b/n);转载地址：http://btvdl.baihongyu.com/