求两个数最大公约数和最小公倍数的简便方法

求两个正整数a,b的最大公约数p和最小公倍数q。

最原始的方法是，p初始化为min(a, b)，这里假设a < b，则p = a，

                              然后检测p能否同时整除a,b，是则停止循环，

                              否则令p -= 1，继续检测

对于q，则将其初始化为max(a,b) = b, 则q = b,

                              检测q能否同时被a和b整除，是则停止循环，

                              否则令q += 1,继续检测

可以看出这样计算效率很低，耗时大，简单的方法是采用欧几里德算法来求最大公约数，而利用(a * b) / p来求最小公倍数。

辗转相除法---欧几里德算法

以计算（1397，2413）的最大公约数为例：

以大数2413为被除数，以小数1397为除数，相除得：商为1，余数为1016

以大数1397为被除数，以小数1016为除数，相除得：商为1，余数为381

以大数1016为被除数，以小数381为除数，相除得：商为2，余数为254

以大数381为被除数，以小数254为除数，相除得：商为1，余数为127

以大数254为被除数，以小数127为除数，相除得：商为2，余数为0

直到能整除，则127就是最大公约数

数学证明：

b = as + r (0 <= r <= b -1)，

若r=0, 显然最大公约数为a；

若r != 0, 由于b = as + r, 每个能整除a,r的整数都能整除b，则它能同时整除a,b

               又，r = b - as, 每个能整除a,b的整数都能整除r，则能整除a,r

因此，a,b的最大公约数和a,r的最大公约数相等。

do{
      r = b % a;
      b = a;
      a = r;
}while(!r)
     

递归的算法：

 

void gcd(int a, int b)
{
    int m;
    if (a > b)
        return gcd(b, a);
    if (b % a != 0)
        return gcd(a, b % a);
    else
        return a;
}