辗转相除法,又被称为欧几里德(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<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; }