利用辗转相除法求最小公倍数，最大公约数

算法简介

辗转相除，又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公约数的算法。它是已知最古老的算法, 其可追溯至公元前300年。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。

算法描述：

两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。

程序实现（C/OC）：

//主程序
int m, n, r;
int s;
m = 24;
n = 36;
s = m * n;

while(n != 0) {
    r = m % n;
    m = n;
    n = r;
}

printf("最小公倍数：%d\n", m);
printf("最大公约数：%d\n", s/m);