什么是最大公约数
最大公约数又称为最大公因数，指两个或多个整数共有约数中最大的一个。
举例来说，9和15的公约数有1、3，其中最大的是3，因此9和15的最大公约数是3。
使用欧几里得算法求最大公约数
欧几里得算法的原理
欧几里得算法，又称辗转相除法，通过求两个数的余数来递归地求它们的最大公约数。
假设a、b为两个整数，且a>b，则有:
a = b × n + m （n和m均为整数，m小于b）
若m=0，则b即为最大公约数；否则，a=b，b=m，再执行上述计算。
欧几里得算法的代码实现
以下是使用C语言实现欧几里得算法求两个数的最大公约数的代码：
#include<stdio.h>
int main(){
int a,b,t,r;
scanf("%d%d",&a, &b);
if(a
t=a;a=b;b=t;
}
r=a%b;
while(r!=0){
a=b;b=r;r=a%b;
}
printf("最大公约数是%d\n",b);
return 0;
}
首先，我们需要输入两个整数a和b，然后使用取模运算符计算它们的余数r。若余数r为0，那么b就是最大公约数。如果余数r不为0，则执行while循环，将原来的b赋给a，余数r赋给b，再次计算b与r的余数。直到余数为0时，b就是最大公约数。
在代码实现时，我们还需要保证a>=b，因为如果a<b，则在第一次取模操作时，r=a，这时程序就会出错。
欧几里得算法的时间复杂度
欧几里得算法的时间复杂度是O(logn)，其中n是a和b的最大值。
为什么欧几里得算法的时间复杂度是O(logn)呢？
我们可以把欧几里得算法的执行过程看成是一个递归的过程：
gcd(a,b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
在每次递归中，除数减少一半以上，因此一共可能会进行O(logn)次递归调用。
使用更相减损术求最大公约数
更相减损术的原理
更相减损术，又称为辗转相减法，通过用较大数减去较小数得到差值，然后用较小数和差值继续相减，不断重复这个过程，直到两个数相等或减数为0，此时这个相等的数或者另一个数就是最大公约数。
举例来说，对于两个数85和51，我们可以使用以下算法求它们的最大公约数：
1. 用较大数85减去较小数51，得到34；
2. 用较小数51和34的差值17继续相减，得到17；
3. 用较小数17和较大数34的差值17相减，得到0，此时两个数相等，它们的最大公约数为17。
更相减损术的代码实现
以下是使用C语言实现更相减损术求两个数的最大公约数的代码：
#include<stdio.h>
int main(){
int a,b;
scanf("%d%d",&a,&b);
while(a!=b){
if(a>b){
a-=b;
}else{
b-=a;
}
}
printf("最大公约数是%d\n",a);
return 0;
}
代码实现中，我们先输入两个整数a和b，然后在while循环中，进行a和b的比较：
如果a>b，我们就用a减去b，并将差值赋给a；
如果a<b，我们就用b减去a，并将差值赋给b。
不断重复这个过程，直到a=b，此时a就是最大公约数。
更相减损术的时间复杂度
更相减损术的时间复杂度是O(n)，其中n是a和b的最大值。
虽然更相减损术的时间复杂度比欧几里得算法高，但是在整数较小的情况下，使用更相减损术比欧几里得算法更加高效。
总结
本文分别介绍了使用欧几里得算法和更相减损术求两个数的最大公约数的原理和代码实现，并对它们的时间复杂度进行了比较。在实际应用中，我们需要根据具体的情况决定使用哪种算法。