利用輾轉相除法求最小公倍數，最大公約數

算法簡介

輾轉相除，又名歐幾裡德算法（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);