C语言最大公约数详解（手把手教你用欧几里得算法求GCD）

在编程学习过程中，C语言最大公约数（GCD）是一个经典且实用的问题。无论你是初学者还是有一定经验的开发者，掌握欧几里得算法（又称辗转相除法）对提升算法思维和解决实际问题都大有裨益。

什么是最大公约数？

最大公约数（Greatest Common Divisor，简称 GCD）是指两个或多个整数共有约数中最大的一个。例如，12 和 18 的最大公约数是 6，因为 6 是能同时整除 12 和 18 的最大整数。

欧几里得算法原理

欧几里得算法是一种高效计算两个正整数最大公约数的方法，其核心思想基于以下定理：

gcd(a, b) = gcd(b, a mod b)，其中 a ≥ b > 0

这个过程不断重复，直到余数为 0，此时的除数就是最大公约数。

C语言最大公约数详解（手把手教你用欧几里得算法求GCD） C语言最大公约数欧几里得算法 C语言GCD实现辗转相除法教程第1张

C语言实现最大公约数

下面我们用 C 语言来实现这个算法。这里提供两种写法：递归版和循环版。

方法一：递归实现

#include <stdio.h>// 递归方式求最大公约数int gcd_recursive(int a, int b) {    if (b == 0)        return a;    return gcd_recursive(b, a % b);}int main() {    int num1 = 48, num2 = 18;    printf("%d 和 %d 的最大公约数是：%d\n",            num1, num2, gcd_recursive(num1, num2));    return 0;}

方法二：循环实现（更节省内存）

#include <stdio.h>// 循环方式求最大公约数int gcd_iterative(int a, int b) {    while (b != 0) {        int temp = b;        b = a % b;        a = temp;    }    return a;}int main() {    int num1 = 48, num2 = 18;    printf("%d 和 %d 的最大公约数是：%d\n",            num1, num2, gcd_iterative(num1, num2));    return 0;}