欧几里得算法（辗转相除法）求最大公约数。最小公倍数

欧几里得算法（辗转相除法）求最大公约数。最小公倍数

1.最大公约数

辗转相除法：求a和b（a>b）的最大公约数，就等同于求 b 和 a mod b的最大公约数。

即为公式：gcd(a,b) ==> gcd(b,a%b) 

推论：

        (1)如果存在一个数d， d|a(d能整除a) 并且 d|b，那么就可以推导出 d|(a+b) 。进一步可以得到 ==> d|(xa+yb)  x,y都是正整数。

d是a和b的最大公约数，现在要求得d也是b和a%b的最大公约数

对于公式 gcd(b,a%b)，a%b 可以转换为  ==> a-(a/b)*b , a/b为整数部分，忽略小数。（例如3/2==>1，抛弃0.5）

也就是说 gcd(b,a%b) 可以转换为 ==> gcd(b , a-(a/b)*b)

a，b最大公约数为d（d能整除a，d能整除b），那么通过(1)可以得到 d 也能整除 a-(a/b)*b（x为1，y为-a/b）。因此d是b和a%b的最大公约数。

例如：

        a=12，b=8，存在一个d为a，b的最大公约数

        gcd(12,8) ==> gcd(8,12%8) ==> gcd(8,12-8) 因为 12除以d为整数，8除以d也为整数，所以4能整除8，所以4就是最大公约数

public static int gcd(int a,int b){return b>0?gcd(b,a%b):a;
}

2.最小公倍数

a，b的最小公倍数等于a，b的乘积除以他们的最大公约数

        最小公倍数也就是能被a和b整除的最小的数。a*b得到的数是倍数但是不一定是最小的公倍数。要怎么保证这个乘积是最小的公倍数？通过去除公共约数就行。

如：a=12,b=8。c=a*b=96。

        a分解成质数为2^2*3^1

        b分解成质数为2^3

        c分解成质数为2^5*3^1

        c要能被a，b整除，只需要c能刚好满足他们包含的质数就行了，也就是c只要有2^3*3^1。但是c的质数2比a和b的质数2都多了，这部分就是冗余的。只要去除冗余部分就能得到最小公倍数了。而这个冗余部分就是最大公约数。

public static int lcm(int a,int b){int gcd = gcd(a, b);return a/gcd*b;
}