更相损减法：
《九章算术·方田》作分数约简時，提到求最大公因数方法：反覆把两数的较大者減去较小者，直至两数相等，这数就是最大公因数。这方法除了把除法换作減法外，与辗转相除法完全相同。例如书中求91和49的最大公因数：
- 91 > 49, 91 - 49 = 42
- 49 > 42, 49 - 42 = 7
- 42 > 7, 42 - 7 = 35
- 35 > 7, 35 - 7 = 28
- 28 > 7, 28 - 7 = 21
- 21 > 7, 21 - 7 = 14
- 14 > 7, 14 - 7 = 7
- 7 = 7, 因此91和49的最大公因数是7
求最大公因数，C++程序代码如下：
#include <iostream>
using namespace std;
int main(void)
{
int num1,num2;
cin>>num1>>num2;
while(num1!=num2)
{
if(num1>num2)
{
num1 = num1 - num2;
}
else
num2 = num2 - num1;
}
cout<<num1<<endl;
return 0;
}
而91与49最小公倍数分析如下：
91 = 7（最大公约数）*13
49 = 7（最大公约数）*7
最小公倍数 = 13*7*7 = 91*49/7(最大公约数），由此能看出，求出最大公约数后，最小公倍数也很快便能得到。
下面用辗转相除法得最大公约数：
若r是num1%num2的余数，max_common_divisor（num1,num2）->max_common_divisor(num2,r),
用递归的方法，当r=0时结束递归。
程序设计如下：
#include <iostream>
using namespace std;
int max_common_divisor(int num1,int num2){
return num2 == 0?num1:max_common_divisor(num2,num1%num2);
}
int main()
{
int num1,num2;
cin>>num1>>num2;
cout<<max_common_divisor(num1,num2)<<endl;
return 0;
}
扩展：
求三个数的最大公约数：
只须在求出的两个数的最大公约数的基础上，再与另一个数求最大公约数即可。
程序代码如下：
#include <iostream>
using namespace std;
int max_common_divisor(int num1,int num2){
return num2 == 0?num1:max_common_divisor(num2,num1%num2);
}
int max_common_divisor2(int result,int num3){
return num3 == 0?result:max_common_divisor2(num3,result%num3);
}
int main()
{
int num1,num2,num3;
int result;
cin>>num1>>num2>>num3;
result = max_common_divisor(num1,num2);
cout<<max_common_divisor2(result,num3)<<endl;
return 0;
}
如果涉及多个数的最大公约数，也可以是递归间的内嵌。即一个递归里面又有一个递归。
程序设计的不足：
更相损减法：当输入的数是零时，会陷入死循环。
辗转相除法：当输入的数是零时，得到的结果总是等于不是零的那个。
解决这种问题，应当对输入的数进行检测，如果检测到有零的输入，应让其重新输入。