最大公约数：也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。（如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数）
最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。
以两个整数为例，我们知道最小公倍数=两整数的乘积/最大公约数。那么在求出最大公约数的基础下，利用该公式便可求出最小公倍数。那么如何求两个数的最大公约数呢？
方法一（试除法）：
我们通常是先比较两个数的大小，找到较小的一个。然后让这两个数都对 以较小数为首的递减序列（增量为-1） 求余，如果两个数同时都能被其整除，则找到最大公约数。
方法二（辗转相减法）：
辗转相减法：不断地对两个数做减法，以此求出最大公约数。即用大数减小数，将所得结果保存到大数中；再用此时的大数减小数，将结果保存到大数中，如此重复，直到最后两数相等，便求出了最大公约数。此方法用得较少。
方法三（辗转相除法）：
辗转相除法是求最大公约数的一种方法，其具体求解思路如下：
两数相除（不论大小），再用除数除以出现的余数（第一余数），再用第一余数除以出现的余数（第二余数），如此反复，直到最后余数是0为止，那么最后的除数便是这两个数的最大公约数。
int gcd(int a,int b){ //辗转相除法，递归实现
if(a%b==0) return b;
return gcd(b,a%b);
}int gcd(int x,int y){//辗转相除的非递归实现，x要大于y
int tmp;
while(y){
tmp=x%y;
x=y;
y=tmp;
}
return x;
}