欧几里得算法来求最大公约数

欧几里得算法，又称辗转相除法，用于求两个正整数的最大公约数。

算法思路：

假设有两个正整数a和b（a>b），求它们的最大公约数gcd(a,b)。

1.用a除以b，得到商q和余数r（a=b*q+r），若r=0，则a和b的最大公约数为b，算法结束；否则，进行下一步。

2.用b除以r，得到商q1和余数r1（b=r*q1+r1），若r1=0，则a和b的最大公约数为r，算法结束；否则，进行下一步。

3.重复上述步骤，直到余数为0，即得到a和b的最大公约数。

简单实现：

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

时间复杂度为O(log(max(a,b)))，空间复杂度为O(1)。