辗转相除法

1997 /615 = 3(余152)
615/ 152 =4(余7)
152/ 7 = 21(余5)
7 / 5 = 1(余2)
5/ 2 = 2(余1)
2/1= 2(余0)

得出1997和615的最大公约数为1。

1. 让大数mod小数
2. 小数mod上一余数，若余数≠0，重复2 （因为是余数，所以一定小于除数）
3. 余数为0，此时的除数为最大公因数，为1，即：互质

int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b, a%b);//return二选一，b为0则a是最大公因数
}//不为则返回递归程序

//若传入a、b值不确定谁大谁小也能传入，因为a%b时，若a<b，返回a
//之后下一个gcd嵌套，将b作为左数，返回的a作为右数，即：位置对调了