最大公约数
：也称最大公约数、最大公因子，指两个或多个
整数
共有约数中最大的一个。（如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数）
最小公倍数
：两个或多个
整数
公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。
以两个整数为例，我们知道最小公倍数=两整数乘积 / 最大公约数。那么在求出最大公约数的基础下，利用该公式便可求出最小公倍数。
那么如何求两个数的最大公约数，最小公倍数呢？
法一：
我们通常是先比较两个数的大小，找到较小的一个。然后让这两个数都对 以较小数为首的递减序列（增量为-1） 求余，如果两个数同时都能被其整除，则找到最大公约数。
int main()
{
int a = 17, b = 35;
int n, i;
//找a,b中较小的数
if (a > b)
{
n = b;
}
else
{
n = a;
}
for ( i = n; i > 0; i--)
{
if (a%i == 0 && b%i == 0)
{
printf("最大公约数为%d\n", i);
printf("最小公倍数为%d\n", (a*b) / i);
break;
}
}
system("pause");
return 0;
}
法二（辗转相减法）：
辗转相减法：不断地对两个数做减法，以此求出最大公约数。即用大数减小数，将所得结果保存到大数中；再用此时的大数减小数，将结果保存到大数中，如此重复，直到最后两数相等，便求出了最大公约数。
以求a = 24和b = 36的最大公约数为例，具体求解思路如下：
1. b=b-a=36-24=12;
2. a=a-b=24-12=12;
3.a=b = 12（此时两数相等） —> 最大公约数为12
代码实现如下：
//辗转相减法求最大公约数,最小公倍数
int main()
{
int a = 28, b = 40;
int mul = a*b;
while (a != b)
{
if (a > b)
{
a = a - b;
}
else if (a < b)
{
b = b - a;
}
}
printf("最大公约数为%d\n", a);
printf("最小公倍数为%d\n", mul/a);
system("pause");
return 0;
}
法三（辗转相除法）：
辗转相除法是求最大公约数的一种方法，其具体求解思路如下：
两数相除（不论大小），再用除数除以出现的余数（第一余数），再用第一余数除以出现的余数（第二余数），如此反复，直到最后余数是0为止，那么最后的除数便是这两个数的最大公约数。
以求24和50的最大公约数为例，具体求解步骤如下：
1. 24%50=24（余数不等于0）
2. 50%24=26（余数不等于0）
3. 24%26=24（余数不等于0）
4. 26%24=2（余数不等于0）
5.24%2=0（余数等于0） —>最大公约数为此时的除数2
代码实现如下：
#include <stdio.h>
#include <windows.h>
int main()
{
int a = 24, b = 50;
int tmp = 0;
int mul = a*b;
while (tmp = a%b)
{
a = b;
b = tmp;
}
printf("最大公约数为%d\n", b);
printf("最小公倍数为%d\n", mul / b);
system("pause");
return 0;
}