C语言求最大公约数

最大公约数是指两个或多个整数共有约数中最大的一个。求最大公约数是数学上的基本问题，这里我们将介绍如何使用C语言来求最大公约数。

C语言求最大公约数

使用辗转相除法求最大公约数

辗转相除法，又称欧几里得算法，是求最大公约数的一种方法，其基本思想是用较大数除以较小数，再用除数除以出现的余数（第一余数），再用第一余数除以出现的余数（第二余数），如此反复，直到最后余数是0为止。

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

上述代码中，使用了递归的方法来实现辗转相除法，如果b等于0，那么最大公约数就是a，否则就继续递归求解。

枚举法是一种朴素的求解方法，即从两个数中较小的数开始，从大到小枚举每一个数，找到两个数的公共因子，直到找到最大的公共因子为止。

int gcd(int a, int b){
    int min = a=1;i--){
        if(a%i==0&&b%i==0){
            return i;
        }
    }
    return 1;
}

最大公约数在数学中应用广泛，例如化简分数、约分、公共倍数等。在程序设计中，求最大公约数也是一种常见的需求，例如在设计密码算法中，常常需要求两个大质数的最大公约数。

辗转相除法的时间复杂度为O(log n)，而枚举法的时间复杂度为O(min(a,b))，因此在处理大数时，辗转相除法更加高效。

负数的最大公约数与正数的最大公约数是一样的，只需要将负数转化为正数即可。例如，-12和18的最大公约数等于12和18的最大公约数。