个人主页：CSDN清风莫追

系列专栏：牛客刷题——数据结构与算法

推荐一款面试、刷题神器牛客网：👉点击开始刷题学习👈

1. 题目

描述如果有一个自然数 a 能被自然数 b 整除，则称 a 为 b 的倍数， b 为 a 的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。

输入 a 和 b , 请返回 a 和 b 的最大公约数。

数据范围： $1\le a,b\le 10^9$

进阶： 空间复杂度 O(1)O(1)，时间复杂度 O(logn)O(logn)

2. 算法设计思路

思路一：简单暴力法我们只需要先比较 a 和 b，将较小的那个值记为 min。然后从 min 开始，逐个整数递减尝试，如果尝试到 i 时可以同时整除 a 和 b，则停止尝试，并返回 i 值。

为什么要从 min 开始递减，而不是从 1 开始递增呢？想一想：我们要求的是最大公约数。思路二：辗转相除法gcd()为求最大公约数的函数反复使用：$gcd(a,b)<=>gcd(b,a$

这里我们不做数学上的证明，有兴趣可以自行网络搜索证明过程。

3. 代码实现

注：这里并不是完整代码，而只是核心代码的模式思路一代码：

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 求出a、b的最大公约数。 * @param a int  * @param b int  * @return int * * C语言声明定义全局变量请加上static，防止重复定义 */int gcd(int a, int b ) {    int min = a > b ? b : a;    for(int i = min; i > 0; i--){        if(a % i ** 0 && b % i ** 0){            return i;        }    }    return -1;}

思路二代码：

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

.

4. 运行结果

成功通过啦！而且可以看到，即使我思路二采用的是递归的写法，运行的效率仍然要高很多。

结束语：

今天的分享就到这里啦，快来加入刷题大军叭！👉点击开始刷题学习👈

感谢阅读