最大公约数：辗转相除法

在数学中， 辗转相除法，又称欧几里得算法，是求最大公约数的算法。

其算法步骤：

例如计算6和4的最大公约数：

1. a=6，b=4，a/b余数为2
2. 将b赋值给a，a=4
3. 将余数赋值给b，b=2
4. b不为0, 重复执行1-3
5. a=4，b=2，a/b余数为0
6. 将b赋值给a，a=2
7. 将余数赋值给b，b=0
8. b为0, 则此时的a为最大公约数

伪代码实现：

function （a, b）
    while b != 0
        t := b
        b := a mod b
        a := t
    return a

c语言实现：

   1: int (int a, int b)

   2: {

   3:     int tmp;

   4:     

   5:     while (b != 0) {

   6:         tmp = b;

   7:         b = a % b;

   8:         a = tmp;            

   9:     }

  10:     

  11:     return a;

  12: }

求得最大公约数之后， 将a与b之积除以最大公约数即为两者的最小公倍数。

即 lcm(a, b) = |a*b| / (a, b)