在C语言里求最大公约数，最常见也最实用的方法是辗转相除法。本文从概念、实现步骤、3种常用写法、完整代码到输入边界处理逐步说明，方便你直接写出能运行、能验证结果的程序。

什么是最大公约数

最大公约数指两个或多个整数共同拥有的最大正因数。在C语言题目中，最常见的是输入两个整数，求它们的最大公约数，也常写作gcd。

例如12和18的公约数有1、2、3、6，其中最大的就是6。理解这个结果后，再去写程序会更清楚：目标不是找所有因数，而是更高效地得到最终答案。

最常用的方法是辗转相除法

辗转相除法也叫欧几里得算法，核心思路是用较大的数除以较小的数，再用除数和余数继续计算，直到余数为0。最后那个非0除数，就是最大公约数。

这种方法比从1开始逐个试除高效得多，代码也短，适合课堂作业、笔试题和实际编程练习。对于大多数C语言基础题，它都是默认优先选择。

1. 设两个整数为a和b，先保证参与运算的是它们的整数值。
2. 当b不等于0时，先保存a % b的结果。
3. 把a更新为b，再把b更新为上一步得到的余数。
4. 循环结束后，a就是最大公约数。

C语言完整示例怎么写

如果你只需要一个稳定、容易看懂的版本，直接使用循环写法即可。它不依赖复杂语法，适合初学者先掌握流程，再理解函数封装和递归写法。

下面的示例包含输入、计算和输出三个部分，并且对两个数同时为0的情况做了单独处理。只要在支持标准C的编译环境中保存并编译，就可以直接测试两个整数的最大公约数结果。

• 完整示例：循环版辗转相除法

  #include 
  
  int gcd(int a, int b) {
      int temp;
  
      if (a < 0) a = -a;
      if (b < 0) b = -b;
  
      while (b != 0) {
          temp = a % b;
          a = b;
          b = temp;
      }
  
      return a;
  }
  
  int main() {
      int a, b;
  
      printf("请输入两个整数：");
      if (scanf("%d %d", &a, &b) != 2) {
          printf("输入错误n");
          return 1;
      }
  
      if (a == 0 && b == 0) {
          printf("两个数同时为0时，最大公约数未定义；本示例按约定输出0。n");
          return 0;
      }
  
      printf("最大公约数是：%dn", gcd(a, b));
      return 0;
  }

• 编译命令：cc -std=c11 gcd.c -o gcd
• 运行命令：./gcd

递归写法与使用时的注意点

如果你已经理解了辗转相除法的循环过程，还可以把它改写成递归函数。递归版本更短，但前提是你已经清楚函数不断调用自身时，参数是怎样变化的。

实际写题时，还要注意负数和0的处理。通常会先把负数转成正数再计算；如果其中一个数为0，另一个非0整数通常就可以直接看作结果。若两个数都为0，严格来说最大公约数未定义，因此最好在主程序里显式判断，并根据题目要求提示或约定输出结果。

递归完整示例

• 完整示例：递归版gcd程序

  #include 
  
  int gcd(int a, int b) {
      if (a < 0) a = -a;
      if (b < 0) b = -b;
      if (b == 0) return a;
      return gcd(b, a % b);
  }
  
  int main() {
      int a, b;
  
      printf("请输入两个整数：");
      if (scanf("%d %d", &a, &b) != 2) {
          printf("输入错误n");
          return 1;
      }
  
      if (a == 0 && b == 0) {
          printf("两个数同时为0时，最大公约数未定义；本示例按约定输出0。n");
          return 0;
      }
  
      printf("最大公约数是：%dn", gcd(a, b));
      return 0;
  }

编写时常见问题

• 测试样例输入：48 18
• 测试样例输入：-24 36
• 测试样例输入：0 15
• 测试样例输入：0 0

第3种常用写法：枚举法

除了循环版和递归版辗转相除法，初学者还常见到枚举法，也就是从较小的数开始向下查找，找到第一个同时整除两个数的整数，就是最大公约数。

这种写法效率不如辗转相除法，但思路直观，适合刚接触最大公约数概念时练习。为了和标题中的“3种常用写法与完整示例”保持一致，下面给出一个可以直接运行的完整程序。

• 完整示例：枚举法程序

  #include 
  
  int gcd_enum(int a, int b) {
      int i;
      int limit;
  
      if (a < 0) a = -a;
      if (b < 0) b = -b;
  
      if (a == 0) return b;
      if (b == 0) return a;
  
      limit = a < b ? a : b;
      for (i = limit; i >= 1; i--) {
          if (a % i == 0 && b % i == 0) {
              return i;
          }
      }
  
      return 1;
  }
  
  int main() {
      int a, b;
  
      printf("请输入两个整数：");
      if (scanf("%d %d", &a, &b) != 2) {
          printf("输入错误n");
          return 1;
      }
  
      if (a == 0 && b == 0) {
          printf("两个数同时为0时，最大公约数未定义；本示例按约定输出0。n");
          return 0;
      }
  
      printf("最大公约数是：%dn", gcd_enum(a, b));
      return 0;
  }

如何判断程序是否写对

判断程序是否正确，不能只看一组普通数字。最好分别测试有公约数、互质、包含负数、包含0这几类输入，确认输出都符合预期。

如果输出不对，优先检查取余顺序、循环结束条件，以及a和b更新时是否写反。这几个地方最容易出错，也是初学者调试最大公约数程序时最常见的问题。两个数同时为0时，还要确认你的程序是否已经按题意做了单独说明：可以提示“未定义”，也可以像本文示例一样明确写出“按约定输出0”。

• 可以先测试12和18，结果应为6。
• 再测试7和13，结果应为1，说明两数互质。
• 测试0和15时，结果通常应为15。
• 测试负数时，要确认程序先完成绝对值处理。
• 测试0和0时，要确认程序是否给出了明确提示或约定结果。

掌握辗转相除法后，c语言求最大公约数这类题目通常都能很快完成。先把循环版写熟，再去理解递归版和枚举法，你会更容易应对作业、考试和基础算法练习。

《夸克》非常好用的免费AI浏览器

下载APP查看