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

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

算法思路：

假设有两个正整数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)。

相关问题

欧几里得递归算法求最大公约数原理

欧几里得递归算法也称为辗转相除法，其原理是利用两个数的最大公约数与其中较小数的余数之间的关系进行递归求解，直到余数为0，此时较大数即为最大公约数。

具体步骤如下：

1. 用两个数中较大的数除以较小的数，得到商和余数。

2. 如果余数为0，则较小的数即为最大公约数。

3. 如果余数不为0，则用较小的数除以余数，得到商和新的余数。

4. 重复步骤3，直到余数为0。

例如，求出42和30的最大公约数，具体步骤如下：

1. 用42除以30，得到商1，余数12。

2. 用30除以12，得到商2，余数6。

3. 用12除以6，得到商2，余数0。

4. 余数为0，因此最大公约数为6。

欧几里得递归算法的时间复杂度为O(logn)，因为每次求余数都会使得问题规模减半，直到余数为0为止。

欧几里得递归算法求最大公约数求时间复杂度

欧几里得算法，也称为辗转相除法，是一种经典的求解两个整数的最大公约数（GCD）的递归算法。其基本思想是利用数学原理：对于任意两个正整数a和b（其中a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。即gcd(a, b) = gcd(b, a % b)。

时间复杂度分析：
- 当输入的两个数a和b大小接近于1时，最多只需要进行一次除法运算（因为b会变为0），此时的时间复杂度是O(1)。
- 对于一般情况，每次递归都会将较大的那个数减小至原来的一半左右，所以最坏情况下，需要递归log(min(a, b))次。每一次递归实际上是一个除法操作加上对较小数的递归，所以总的时间复杂度近似为O(log n)，n为较小的那个数。

因此，尽管看起来递归可能会导致指数级的增长，但由于每一步都减少了一个数量级，实际运行效率相当高。这就是为什么欧几里得算法通常被认为是计算GCD的有效方法之一。