C语言求最大公约数（欧几里得算法）

欧几里得算法的思想基于辗转相除法的原理，其原理为：假设两数为 a、b(b<a)，用 gcd(a，b) 表示 a、b 的最大公约数，r=a mod b，r 为 a 除以 b 以后的余数，k 为 a 除以 b 的商，即 a÷b=k…r。辗转相除法是欧几里得算法的核心思想。

欧几里得算法的操作步骤如下。

• 令 c 为 a 和 b 的最大公约数，数学符号表示为 c=gcd(a，b)。因为任何两个实数的最大公约数 c 一定是存在的，也就是说必然存在两个数 k1、k2 使 a=k1*c，b=k2*c。
• a mod b 等价于存在整数 r，k3 使余数 r=a–k3*b，即 r=a–k3*b=k1*c–k3*k2*c=(k1–k3*k2)*c。

显然，a 和 b 的余数 r 是最大公因数 c 的倍数。

通过模运算的余数与最大公约数之间存在的整数倍的关系，来给比较大的数字进行降维，便于手动计算；同时，也避免了在可行区间内进行全局最大公约数的判断测试。

只需选取其余数进行相应的计算就可以直接得到最大公约数，大大提高了运算效率。

示例

利用欧几里得算法，求任意两个正整数的最大公约数。C语言编程代码如下：

#include<stdio.h>
unsigned int gcd(unsigned int m,unsigned int n)
{
    unsigned int rem; /*定义一个无符号整型变量*/
    while(n > 0)                 /*辗转相除法*/
    {
        rem = m % n;           /*取余操作*/
        m = n;
        n = rem;
    }
    return m;
}
int main(void)
{
    int a,b;
    printf("请输入任意两个正整数：\n");
    scanf("%d %d",&a,&b);
    printf("%d和%d的最大公约数是： ",a,b);
    printf("%d\n",gcd(a,b));        /*输出结果值*/
    return 0;
}

运行结果：

请输入任意两个正整数：
28 30
28和30的最大公约数是： 2

本例着重介绍了C语言求最大公约数（欧几里得算法）。当 a>b 时，有两种情况，b<=a/2，gcd(a，b) 变为 gcd(b，a%b)；b>a/2，则 a%b。经过迭代，gca(a，b) 的数据量减少了一半。