在C语言里求最大公约数，常见做法不止一种。本文围绕c语言求最大公约数方法，分别说明辗转相除法、更相减损术和递归写法的适用场景、实现步骤与完整示例，方便直接上手。

先弄清最大公约数要解决什么问题

最大公约数指两个或多个整数都能整除的最大正整数。在C语言题目里，最常见的是输入两个整数，输出它们的最大公约数，因此核心不在界面，而在求解过程是否正确。

如果题目只是课堂练习，通常要求写出函数并打印结果；如果放到工程代码里，还要考虑输入为0、负数处理以及函数是否便于复用。先明确这些边界，再选方法会更稳妥。

3种常用求法各适合什么场景

大多数情况下，辗转相除法是首选，因为代码短、运行快、思路也最清晰。只要你会使用取模运算，这种写法通常最适合作为标准答案。

更相减损术不依赖取模，适合刚接触算法、想先理解公约数变化规律的人。递归写法则更简洁，但前提是你已经能接受函数不断自我调用的执行过程。

1. 辗转相除法：通过不断用较大数除以较小数并取余，直到余数为0，最后的除数就是最大公约数。
2. 更相减损术：反复让较大数减去较小数，直到两个数相等，这个相等的值就是结果。
3. 递归写法：本质仍然是辗转相除法，只是把循环过程改写成函数递归调用。

辗转相除法的实现步骤与完整示例

实现时先准备两个整数a和b。只要b不等于0，就把a除以b得到余数，再让a接收原来的b，让b接收余数，如此循环，直到b变成0，a就是答案。

这种方法的优势是迭代次数少，面对较大的整数也能很快算出结果。对初学者来说，只要把变量更新顺序写对，基本不会出大问题。为了让边界更清楚，下面示例把a和b同时为0时约定为返回0，表示这组输入不再继续计算。

• 完整示例

  #include 
  
  int gcd(int a, int b) {
      int temp;
  
      if (a < 0) a = -a;
      if (b < 0) b = -b;
  
      if (a == 0 && b == 0) {
          return 0;
      }
  
      while (b != 0) {
          temp = a % b;
          a = b;
          b = temp;
      }
  
      return a;
  }
  
  int main(void) {
      int a, b;
  
      printf("请输入两个整数：");
      if (scanf("%d%d", &a, &b) != 2) {
          printf("输入错误n");
          return 1;
      }
  
      if (a == 0 && b == 0) {
          printf("0和0没有实际意义，示例中约定返回0n");
      } else {
          printf("最大公约数是：%dn", gcd(a, b));
      }
  
      return 0;
  }

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

更相减损术的实现步骤与完整示例

更相减损术的写法重点在于持续比较两个数的大小。如果a和b都不是0，就先把它们转成非负数；接着只要a和b不相等，就让较大的那个数减去较小的那个数，直到两者相等为止。最后这个相等的值就是最大公约数。

这种方法不需要取模运算，适合用来帮助理解公约数在等价变换中的保持关系。为了便于直接套用，下面的代码同样补上了负数处理，以及a和b同时为0时返回0的约定。

• 完整示例

  #include 
  
  int gcd_sub(int a, int b) {
      if (a < 0) a = -a;
      if (b < 0) b = -b;
  
      if (a == 0 && b == 0) {
          return 0;
      }
      if (a == 0) {
          return b;
      }
      if (b == 0) {
          return a;
      }
  
      while (a != b) {
          if (a > b) {
              a = a - b;
          } else {
              b = b - a;
          }
      }
  
      return a;
  }
  
  int main(void) {
      int a, b;
  
      printf("请输入两个整数：");
      if (scanf("%d%d", &a, &b) != 2) {
          printf("输入错误n");
          return 1;
      }
  
      if (a == 0 && b == 0) {
          printf("0和0没有实际意义，示例中约定返回0n");
      } else {
          printf("最大公约数是：%dn", gcd_sub(a, b));
      }
  
      return 0;
  }

• 示例输入输出：输入：12 18 输出：最大公约数是：6

递归写法的实现步骤与完整示例

递归版可以看成把辗转相除法的循环过程塞进函数自身。写的时候先定义一个gcd函数，再明确终止条件：当b等于0时，直接返回a；否则就返回gcd(b, a % b)。只要这两个步骤写对，代码会很短。

递归写法适合已经熟悉函数调用的人，因为它表达简洁，但调试时要能看懂每一层调用的返回过程。和前两种方法一样，下面示例也对负数做了绝对值处理，并明确了0和0时返回0。

• 完整示例

  #include 
  
  int gcd_recursive(int a, int b) {
      if (a < 0) a = -a;
      if (b < 0) b = -b;
  
      if (a == 0 && b == 0) {
          return 0;
      }
      if (b == 0) {
          return a;
      }
  
      return gcd_recursive(b, a % b);
  }
  
  int main(void) {
      int a, b;
  
      printf("请输入两个整数：");
      if (scanf("%d%d", &a, &b) != 2) {
          printf("输入错误n");
          return 1;
      }
  
      if (a == 0 && b == 0) {
          printf("0和0没有实际意义，示例中约定返回0n");
      } else {
          printf("最大公约数是：%dn", gcd_recursive(a, b));
      }
  
      return 0;
  }

• 示例输入输出：输入：25 10 输出：最大公约数是：5

写代码时容易出错的地方

很多人并不是不会算法，而是把细节写错了。最常见的问题是更新变量顺序错误，导致余数还没保存就被覆盖，最后得到的结果不正确。

另一个高频问题是没有处理负数和0。如果输入里可能出现负数，最好先转成正数；如果其中一个数为0，按照常见处理方式，结果通常取另一个数的绝对值。如果a和b同时为0，本文示例统一约定返回0，并在主函数里单独提示这组输入没有实际计算意义，这样边界更明确。

• 把临时变量放在取余结果上，避免先改a后无法得到正确余数。
• 循环条件写成b != 0，不要误写成a != 0，否则结束时机可能不对。
• 测试时至少检查12和18、25和10、0和8、-16和24、0和0这几类输入，便于发现边界问题。

该怎么选择最适合自己的写法

如果你的目标是完成作业、笔试或机试，优先掌握辗转相除法的循环版。它最稳、最常见，也最容易向老师或面试官解释清楚执行过程。

如果你还在打基础，可以顺带理解更相减损术，帮助自己真正明白为什么公约数不会在变换中丢失。等你对函数调用更熟悉后，再把同样思路改成递归版，会更容易建立算法表达能力。

掌握c语言求最大公约数方法，关键不是背一段代码，而是理解余数迭代为什么能不断逼近结果。把辗转相除法、更相减损术和递归版都亲手写一遍，再把0和0这类边界约定补清楚，日常练习和考试场景就更完整了。

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

下载APP查看