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语言中求最大公约数。在实际使用的过程中，可以根据需求选择不同的方法，以便获得更高的效率和更快的速度。