欧几里德算法又称辗转相除法鼡于计算两个整数a,b的最大公约数。
假设d是a,b的一个公约数则有
因此d也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等得证
最简单的方法就是应用递归算法,代码如下:
当然你也可以用迭代形式: