编程之美2.7 最大公约数、最小公倍数

方法一：辗转相除法                                                                                                       点击此处返回总目录

方法二：使用减法操作

方法三：使用位运算和减法操作

最大公约数（greatest common divisor）、最小公倍数（least common multiple）。

1. 求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。

2. a,b的最大公约数gcd(a,b)与最小公倍数lcm(a,b)的关系是：

    gcd(a,b) *  lcm(a,b) = a*b 

方法一、辗转相除法求最大公约数

【方法】

假设a>b，a除以b余数为c（c!=0）。则 a与b的最大公约数 = b与c的最大公约数。即：

gcd(a,b) = gcd(b,c)

比如要求6105和2146的最大公约数。求法如下：

6105＝2146×2＋1813        6105与2146的最大公约数等于2146与1813的最大公约数
2146＝1813×1＋333          2146与1813的最大公约数等于1813与333的最大公约数
1813＝333×5＋148            1813与333的最大公约数等于333与148的最大公约数
333＝148×2＋37                333月148的最大公约数等于148与37的最大公约数
148＝37×4＋0                    148月37的最大公约数为37。（除尽）。
因此37为8251与6105的最大公因数。

【证明】

我简单的证明一下࿱