辗转相除法，又被称为欧几里德（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。 辗转相除法是一种递归算法。
算法实现： 递归版本：
代码语言：javascript复制 private static int gac(int a, int b) {
if(a<b){
swap(a,b);
}
if(b==0)
return a;
else
return gcd(b,a%b);
}
private static void swap(int a, int b) {
a=a^b;
b=a^b;
a=a^b;
}循环版本：
代码语言：javascript复制private static int gac(int a, int b) {
if(a<b){
swap(a,b);
}
while(b!=0){
int c = a%b;
a=b;
b=c;
}
return a;
}
private static void swap(int a, int b) {
a=a^b;
b=a^b;
a=a^b;
}2个数a,b;已知最大公约数为n； 最小公倍数=a*(b/n);
