欧几里德法求最大公约数

最大公约数，Greatest Common Divisor，简称GCD。最早接触的求最大公约数的方法应该是小学期间 -- 凭感觉取一个公约数作为除数，让需要求最大公约数的数相除，除得的余数再凭感觉取一个公约数作除数，直至余数无公约数。最后将所有除数相乘就是最大公约数。

这里介绍公元前就提出的一种方法 -- 欧几里德法。

欧几里德法又名辗转相除法，由古希腊数学家欧几里德提出。

依赖的数学定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

假设 a > b, 不用这个条件照样成立，试着想一下
递归形式

gcd(a, b){
	if( a % b == 0 ) return b
	return gcd(b, a%b)
}

循环形式

while(b!=0){
	temp = a%b
	a=b
	b=temp
}

最大公约数为a