特点及意义
最大公约数指某几个整数共有因子中最大的一个。
GCD即Greatest Common Divisor.
例如，12和30的公约数有：1、2、3、6，其中6就是12和30的 最大公约数。
两个整数的最大公约数主要有两种寻找方法：
* 两数各分解质因子，然后取出同样有的项乘起来
* 辗转相除法（扩展版）
和最小公倍数（lcm）的关系：gcd(a, b)×lcm(a, b) = ab
两个整数的最大公因子可用于计算两数的最小公倍数，或分数化简成最简分数。
两个整数的最大公因子和最小公倍数中存在分配律：
* gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
* lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))
在坐标里，将点(0, 0)和(a, b)连起来，通过整数坐标的点的数目（除了(0, 0)一点之外）就是gcd(a, b)。
gcd递归定理及证明
gcd递归定理是指gcd(a,b)=gcd(b,a%b),其中%表示取余数。
证明如下：
我们只需证明gcd(a,b)和gcd(b,a%b)可以互相整除即可。
对于gcd(a,b)，它是a和b的线性组合中的最小正元素，gcd(b,a%b) 是b与a%b的一个线性组合，而a%b是a与b的一个线性组合，因而gcd(b,a%b)是一个a与b的线性组合，因为a,b都能被gcd(a,b)整除，因而任何一个a与b的线性组合都能被gcd(a,b)整除，所以gcd(b,a%b)能被gcd(a,b)整除。反之亦然。
代码语言：javascript复制// gcd.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
int gcd(int a ,int b)
{
int c = 0;
if (a < b)
{
c = a ;a = b; b= c;//把大的元素放在前面
}
for (;a - b >= 0 ;b = a - b,a = c)
{
if (a % b == 0)
{
return b;
}
c = b;
}
}
unsigned int gcd(unsigned int a,unsigned int b)
{
int r;
while(b>0)
{
r=a%b;
a=b;
b=r;
}
return a;
}
unsigned int gcd1(unsigned int a,unsigned int b)
{
while(b^=a^=b^=a%=b);
return a;
}
unsigned int gcd2(unsigned int a,unsigned int b)
{
return (b>0)?gcd(b,a%b):a;
}
int _tmain(int argc, _TCHAR* argv[])
{
int b = gcd(4,12);
return 0;
}
