C语言程序设计教程（第三版）课后习题6.1 （C++代码）

解题思路:

要解这道题，首先我们要了解，最大公因数和最小公倍数的相关性质：两数的乘积除以最大公因数就是最小公倍数，以及数学界的相关解法。

所以要求最大公因数和最小公倍数，只需求出其一就可直接利用性质，完成题目。

以下介绍一下求最大公因数的一种古老的方法：

辗转相除法

早在公元前300年左右，欧几里得就在他的著作《几何原本》中给出了高效的解法——辗转相除法。辗转相除法使用到的原理很聪明也很简单，假设用f（x, y）表示x，y的最大公约数，取k = x/y，b = x%y，则x = ky + b，如果一个数能够同时整除x和y，则必能同时整除b和y；而能够同时整除b和y的数也必能同时整除x和y，即x和y的公约数与b和y的公约数是相同的，其最大公约数也是相同的，则有f（x, y）= f（y, x%y）（y > 0），如此便可把原问题转化为求两个更小数的最大公约数，直到其中一个数为0，剩下的另外一个数就是两者最大的公约数。

例如，12和30的公约数有：1、2、3、6，其中6就是12和30的最大公约数。

辗转相除法是古希腊求两个正整数的最大公约数的，也叫欧几里德算法，其方法是用较大的数除以较小的数，上面较小的除数和得出的余数构成新的一对数，继续做上面的除法，直到出现能够整除的两个数，其中较小的数（即除数）就是最大公约数。以求288和123的最大公约数为例，操作如下：

288÷123=2余42

123÷42=2余39

42÷39=1余3

39÷3=13

所以3就是288和123的最大公约数。

注意事项:

辗转相除法在编程的实现，一个弊端就是必须是用大数对小数取余，所以要提前用条件语句判断三种可能情况

因为变量数较多，或者会有重复使用先前变量的步骤，而先前变量可能被改变，所以要提前用一些中间变量储存先前变量的值。

参考代码:

#include<iostream>
using namespace std ;
int main()
{
	int t = 1 ;//取余计算的余数，赋值为1是为了方便进入while循环
	int m,n ;
	cin>>m>>n ;
	int nNum1 = m ;//中间变量：保存m
	int nNum2 = n ;//中间变量：保存n
	if(m > n)//判断两数的大小，保证用大数对小数取余
	{
		while(t != 0)
		{
			t = m % n ;
			m = n ;//将随后循环中的m变成本次循环计算后的n
			n = t ;//将随后循环中的n变成本次循环计算后的t
		}
		int b = (nNum1 * nNum2) / m ;//利用性质求出最小公倍数
		cout<<m<<" "<<b<<endl ;
	}
	else if(m < n)
	{
		while(t != 0)
		{
			t = n % m ;
			n = m ;
			m = t ;
		}
		int b = (nNum1 * nNum2) / n ;
		cout<<n<<" "<<b<<endl ;
	}
	else//当m=n时，最大公因数和最小公倍数相等，都等于他们本身
	{
		cout<<n<<" "<<n<<endl ;
	}
	
	return 0 ;
}