求两个正整数m和n的最大公约数

用辗转相除法

用短除法

求两个正整数的最大公约数的算法通常使用“辗转相除法”。设有两个正整数m、n，求它们的最大公约数的算法如下：
①若m＜n，则交换m和n（保证m大于n）。
②计算m/n的余数r。
③若r不等于0，则令m＝n、n＝r，转第②步继续执行；
否则，算法结束，n就是最大公约数。
下面就是用“辗转相除法'才出并返回m、n最大公约数的函数fmn（），请填写清单中缺少的语句。
int fmn（ m, n）
int m， n；
｛ int r；
if（m＜n ）
{r＝m；m＝n；n＝r；}
if（n＝＝0）
return（m）；
do{_________________
if（r!= 0）
{ m＝n； n＝r；}
}while（r!=0）；
return（n）；
}
【分析】由于算法步骤已经给出，按照算法来理解程序就比较简单。函数体开始的单分支语
句是确保m值是大于n值的。接下来的单分支语句是确保算法中的除法“m／n”时的除数n不为0。注意，如果一开始的n就是O，则两个最大公约数就是m，此处利用返回语句返回的函数值就是m。接下来的do－while循环是实现算法步骤中的第②步和第③步的，显然该循环体中的第2条单分支语句是完成算法步骤中的第③步工作的，而空白处应该完成算法步骤中的第②步工作，即r等于m／n的余数。
【答案】r＝m％n；
【说明】求最大公约数和最小公倍数的算法是常用算法；但在教材中并没有给出，希望读者在
学有余力的情况下，能掌握这两个算法。
求两个正整数的最小公倍数的算法在教材中也没有给出，下面给出求最小公倍数的一种算法。设有两个正整数m、n，求它们的最小公倍数的算法如下：
①若m＜n，则交换m和n（保证m大于n）。
②令d＝m。
③若d能被n整除，则算法结束，d就是m和n的最小公倍数。
否则，令d＝d＋m，转第③步，继续执行。
实现算法的程序清单如下：
m