輾轉相除法_歐幾裡得算法_java的實作（求最大公約數）

輾轉相除法，又被稱為歐幾裡德（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。

　　輾轉相除法是一種遞歸算法。

算法實作：

遞歸版本：

循環版本：

2個數a,b;已知最大公約數為n；

最小公倍數=a*(b/n);