C语言求最大公约数

　　最大公约数在数学中非常重要，它是在求两个数的最大公因数的同义词。而在C语言中，求最大公约数有多种方法。

　　方法一：暴力枚举法

　　暴力枚举法就是枚举从2到两个数中较小的一个数，看他们是否能够同时整除已知的两个数。若找到符合条件的就输出，否则输出1。由于最小的公约数是1，所以最坏的情况下遍历整个数组。

　　C语言代码如下：

　　```c

　　#include

　　int gcd(int a,int b){

　　 int i,min;

　　 min=a

　　 for(i=min;i>1;i--) //枚举从2到最小值

　　 if(a%i==0&&b%i==0) //当i可同时整除两个数的时候则跳出循环

　　 break;

　　 if(i==1) //当枚举到1时，两个数没有公共的约数

　　 return 1;

　　 else

　　 return i;

　　}

　　void main(){

　　 int a,b;

　　 printf("请输入两个整数：");

　　 scanf("%d%d",&a,&b);

　　 printf("%d和%d的最大公约数是：%d",a,b,gcd(a,b));

　　}

　　```

　　方法二：辗转相除法

　　辗转相除法（又称欧几里得算法）是求两个非负整数的最大公约数的一种方法，其基本思想是用较大数除以较小数，再用出现的余数去除较小数（第一次除数是10，余数是6，第二次除数是6，余数是4，第三次除数是4，余数是2，第四次除数是2，余数是0，则最大公约数为2），如此反复，直到余数是0为止；此时，负数的除数即为这两个数的最大公约数。

　　C语言代码如下：

　　```c

　　#include

　　int gcd(int a,int b){

　　 return b==0?a:gcd(b,a%b);

　　}

　　void main(){

　　 int a,b;

　　 printf("请输入两个整数：");

　　 scanf("%d%d",&a,&b);

　　 printf("%d和%d的最大公约数是：%d",a,b,gcd(a,b));

　　}

　　```

　　方法三：更相减损法

　　更相减损法又叫减法求最大公约数，是公元前3世纪中国的一位叫做朱世杰的数学家发明的。more subtract less法的名字说明了它是利用较大的数减去较小的数，然后用得到的差值再去减较小的数。在大约17世纪的欧洲，更相减损法被广泛应用，直到1760年代表了上限的辗转相除法才开始替代更相减损法。

　　C语言代码如下：

　　```c

　　#include

　　int gcd(int a,int b){

　　 if(a==b)

　　 return a; //当两个数相同时，返回任意一个数

　　 if((a&1)==0&&(b&1)==0) //两个数是偶数时，最大公约数也是2的倍数，将两个数同时除以2

　　 return gcd(a>>1,b>>1)<<1; //递归调用

　　 if((a&1)==0&&b&1!=0) //若a是偶数，b是奇数，则将a除以2

　　 return gcd(a>>1,b);

　　 if((a&1)!=0&&b&1==0) //若a是奇数，b是偶数，则将b除以2

　　 return gcd(a,b>>1);

　　 int big=a>b?a:b;

　　 int small=a+b-big;

　　 return gcd(big-small,small);

　　}

　　void main(){

　　 int a,b;

　　 printf("请输入两个整数：");

　　 scanf("%d%d",&a,&b);

　　 printf("%d和%d的最大公约数是：%d",a,b,gcd(a,b));

　　}

　　```

　　以上三种方法都可以用于C语言中求最大公约数。在实际使用的过程中，可以根据需求选择不同的方法，以便获得更高的效率和更快的速度。