C 練習實例16 - 最大公約數(shù)和最小公倍數(shù)

C 語言經(jīng)典100例 C 語言經(jīng)典100例

題目：輸入兩個正整數(shù)m和n，求其最大公約數(shù)和最小公倍數(shù)。

程序分析：

（1）最小公倍數(shù)=輸入的兩個數(shù)之積除于它們的最大公約數(shù)，關(guān)鍵是求出最大公約數(shù)；

（2）求最大公約數(shù)用輾轉(zhuǎn)相除法（又名歐幾里德算法）

1）證明：設(shè)c是a和b的最大公約數(shù)，記為c=gcd(a,b),a>=b,
令r=a mod b
設(shè)a=kc，b=jc，則k，j互素，否則c不是最大公約數(shù)
據(jù)上，r=a-mb=kc-mjc=(k-mj)c
可知r也是c的倍數(shù)，且k-mj與j互素，否則與前述k，j互素矛盾,
由此可知，b與r的最大公約數(shù)也是c，即gcd(a,b)=gcd(b,a mod b)，得證。

2）算法描述：

第一步：a ÷ b，令r為所得余數(shù)（0≤r