本文共 649 字，大约阅读时间需要 2 分钟。

int GreatestCommonDivisor(int a, int b) {    int t;     if (a < b) {        // 交换两个数，使大数放在a的位置上。        t = a;        a = b;        b = t;    }     while (b != 0) {        // 利用辗转相除法，直到b为0为止。        t = a % b;        a = b;        b = t;    }     return a;} int LeastCommonMultiple(int a, int b) {    int t = a * b / GreatestCommonDivisor(a, b);    return t;}

1. 反复a%b得到余数为0时候，就可以得到最大公约数，为什么呢，因为如下：（利用最大公约数不会超过小的那个数的性质）简单来说，被除数被分成了两坨，一坨可以被除数整除，一坨是余数，现在都可以被整除的玩意必然也可以被最后的最大公约数整除，所以只用找余数与除数的最大公因数，然后同理，余数与除数又分别成了被除数和除数，直至最后整除。
2. 设两个数为ak bk
   k为最大公约数 则最小公倍数为abk，因为最小公倍数m的意思就是m除以ak，bk分别得到的数不能再进行约下去了，而abk/ak=b，abk/bk=a，a和b根据最大公约数定义即第一步，是不能再相约了的，因此这个abk就是最小公倍数。

转载地址：http://xacr.baihongyu.com/