输入两个正整数m和n 求其最大公约数和最小公倍数

求最小公倍数算法：

最小公倍数 = 两整数的乘积 ÷ 最大公约数

根据求最小公倍数的算法，可以看出如果已知最大公约数，就能很容易求出最小公倍数。而通过辗转相除法和相减法，可以求得最大公约数，下面分别进行介绍。

辗转相除法

已知有两整数m和n，利用辗转相除法求它们的最大公约数，具体步骤如下：

①m%n得余数t； ② 若t=0，则n即为两数的最大公约数；

③ 若t≠0，则m=n，n=t，再回去执行①。

举例说明：

已知m = 21 n = 28，辗转相除法步骤如下：

① 执行t = m%n = 21%28 = 21， 则t = 21，此时t不为0，进入循环；

② 先执行m = 28 ，n = 21，再执行t = m%n = 28%21 = 7，则t = 7，此时t不为 0；

③ 先执行m = 21 , n = 7，再执行t = m%n = 21%7 = 0，则t = 0，循环结束，n=7为最大公约数。

int m,n,t;scanf("%d%d",&m,&n);t = m % n;while( t ){m = n;n = t;t = m%n;}

相减法

已知有两整数m和n，利用相减法求它们的最大公约数，具体步骤如下：

① 若m > n，则m = m-n； ② 若m < n，则n = n-m； ③ 若m = n，则m（或n）即为两数的最大公约数；

④ 若m ≠ n，则再回去执行①。

例如求m=27和n=15的最大公约数过程为：

①m = 27－15 = 12 n = 15

②m = 12 n = 15-12 = 3

③m = 12-3 = 9 n=3

④m = 9-3 = 6 n=3

⑤m = 6-3 = 3 n=3

因此，n = 3即为最大公约数。

int m,n,t;scanf("%d%d",&m,&n);while(m!=n){if(m>n)m=m-n;elsen=n-m;}

下面附相关数学知识

辗转相除法

辗转相除法：辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。

例如，求（319，377）：

∵ 319÷377=0（余319）

∴（319，377）=（377，319）；

∵ 377÷319=1（余58）

∴（377，319）=（319，58）；

∵ 319÷58=5（余29）

∴ （319，58）=（58，29）；

∵ 58÷29=2（余0）

∴ （58，29）= 29；

∴ （319，377）=29。

可以写成右边的格式。

用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。

更相减损法

更相减损法：也叫更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

翻译成现代语言如下：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

例1．用更相减损术求98与63的最大公约数。

解：由于63不是偶数，把98和63以大数减小数，并辗转相减：

98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以，98和63的最大公约数等于7。

这个过程可以简单的写为：

（98，63）=（35，63）=（35，28）=（7，28）=（7，21）=（7，14）=（7，7）=7.

例2．用更相减损术求260和104的最大公约数。

解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。

此时65是奇数而26不是奇数，故把65和26辗转相减：

65-26=39

39-26=13

26-13=13

所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即13*2*2=52。

这个过程可以简单地写为：

（260,104）(/2/2) =>（65,26）=（39,26）=（13,26）=（13,13）=13. (*2*2) => 52[1]

比较辗转相除法与更相减损术的区别

（1）都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。

（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。

在解有关最大公约数、最小公倍数的问题时，常用到以下结论：

（1）如果两个自然数是互质数，那么它们的最大公约数是1，最小公倍数是这两个数的乘积。

例如8和9，它们是互质数，所以（8，9）=1，[8，9]=72。

（2）如果两个自然数中，较大数是较小数的倍数，那么较小数就是这两个数的最大公约数，较大数就是这两个数的最小公倍数。

例如18与3，18÷3=6，所以（18，3）=3，[18，3]=18。

（3）两个整数分别除以它们的最大公约数，所得的商是互质数。

例如8和14分别除以它们的最大公约数2，所得的商分别为4和7，那么4和7是互质数。

（4）两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积。

例如12和16，（12，16）=4，[12，16]=48，有4×48=12×16，即（12，16）× [12，16]=12×16。

（5）GCD(a,b) is the smallest positive linear combination of a and b. a与b的最大公约数是最小的a与b的正线性组合,即对于方程xa+yb=c来说,若x,a,y,b都为整数,那么c的最小正根为gcd(a,b).