1 定义
最大公约数
greatest common divisor，简写为gcd；或highestcommon factor，简写为hcf
如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。
例： 在2、4、6中，2就是2，4，6的最大公约数。
最小公倍数
最小公倍数（Least Common Multiple，缩写L.C.M.）
最小公倍数=两数的乘积/最大公约数
欧几里德算法（辗转相除法）
1. 欧几里德算法和扩展欧几里德算法
1). 欧几里德算法
欧几里德算法又称辗转相除法，
用于计算两个整数a, b的最大公约数。其计算原理依赖于下面的定理：
定理： gcd(a, b) = gcd(b, a mod b)
证明：
a可以表示成a = kb + r, 则r = a mod b
假设d是a, b的一个公约数， 则有 d|a, d|b, 而r = a - kb, 因此d|r。
因此，d是(b, a mod b)的公约数。
加上d是(b，a mod b)的公约数，则d|b, d|r, 但是a = kb + r,因此d也是(a, b)的公约数。
因此，(a, b) 和(a, a mod b)的公约数是一样的，其最大公约数也必然相等，得证。
//-------------------------------------------
//算法1：欧几里德算法（辗转相除法），求最大公约数，时间复杂度O(logn)
//递归算法
public long long gcd(long long x, long long y) {
if( y==0) //base case
return x;
else
return gcd(y, x%y);
} //end gcd()
//非递归算法
public long gcd(int x,int y) {
int temp;
while(y!=0) { //base case :
temp=x%y;
x=y;
y=temp;
} //end while
return x;
} //end gcd()
//-------------------------------------------------------------------
//最小公倍数=两数的乘积/最大公约数，所以可在最大公约数的基础上求最小公倍数
public long lcm(int x,int y){
long gcd=gcd(x,y);
return (x*y)/gcd;
}//end lcm()
//-------------------------------------------
2.
Stein算法
欧几里德算法是计算两个数最大公约数的传统算法，无论是理论，还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在很大的素数时才会显现出来。
考虑现在的硬件平台，一般整数最多也就是64位， 对于这样的整数，计算两个数值就的模很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。
Stein算法由J.Stein 1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。
为了说明Stein算法的正确性，首先必须注意到以下结论：
gcd(a, a) = a， 也就是一个数和他自己的公约数是其自身。
gcd(ka, kb) = k * gcd(a, b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数比如能被2整除。
Stein算法的python实现如下：
def gcd_Stein(a, b):
if a < b:
a, b = b, a
if (0 == b):
return a
if a % 2 == 0 and b % 2 == 0:
return 2 * gcd_Stein(a/2, b/2)
if a % 2 == 0:
return gcd_Stein(a / 2, b)
if b % 2 == 0:
return gcd_Stein(a, b / 2)
return gcd_Stein((a + b) / 2, (a - b) / 2)
算法2
算法2：按照定义求解最大公约数和最小公倍数，从i=1每次加1到x和y中的较小的那个值，然后求能同时整除x和y的i值，这个过程是上图中的过程
最大公约数JAVA代码
public long gcd(int x,int y){
//获取两数较小值
if(x>y){
int temp=x;
x=y;
y=temp;
}//end if
int result=1; //最大公约数结果
for(int i=2;i<=x;i++){
if( (x%i==0) && (y%i==0) ){
result*=i;
x=x/i;
y=y/i;
}//end if
}//end for
return result;
}//end gcd()
最小公倍数：最小公倍数为最大公约数乘以最后的x和y值（），上述图中过程
public long lcm(int x,int y){
//获取两数较小值
if(x>y){
int temp=x;
x=y;
y=temp;
}//end if
int result=1;
for(int i=2;i<=x;i++){
if( (x%i==0) && (y%i==0) ){
result*=i;
x=x/i;
y=y/i;
}//end if
}//end for
return result=result*(x*y);
}//end lcm()
【Google 2012校招笔试】求最大公约数
以下程序是用来计算两个非负数之间的最大公约数：
long long gcd(long long x, long long y) {
if( y==0) return 0;
else return gcd (y, x%y);
}
我们假设x,y中最大的那个数的长度为n，基本运算时间复杂度为O(1)，那么该程序的时间复杂度为：
A.O(1) B.O(logn) C.O(n) D.O(n^2)
【分析】选B.求最大公约数用的是辗转相除法（欧几里得算法），所以是O(logn)。
参考文献: