如何求解最大公约数

最大公约数是指两个或多个整数共有约数中最大的一个，简称公约数最大公因数，通常使用字母（a，b）来表示，也可以用其他字母来表示。

一、辗转相减法

辗转相减法，又称为欧几里德算法，具体的步骤如下：

1. 用大数减去小数，接着用得到的差值去减小的数，一直一直重复，直到减数和差值相等时算法结束；
2. 这个最大公约数就是每次得到的差值；

具体的解法请参考以下代码，以求解a=50,b=15为例：

// 辗转相减法求最大公约数 int gcd(int a, int b) {   while (a != b) {     if (a > b) a = a - b;     else b = b - a;   }   return a; }   int main() {   int a = 50, b = 15;   int result = gcd(a, b);   printf("%d", result);   return 0; }  

二、辗转相除法

辗转相除法，也称为欧几里德算法，具体的步骤如下：

1. 用除数除以余数，接着用得到的余数去除先前的除数，一直重复这个过程，直到余数为0，则此时的除数就是最大公约数。

具体的解法请参考以下代码，以求解a=50,b=15为例：

// 辗转相除法求最大公约数 int gcd(int a, int b) {   if (b == 0) return a;   return gcd(b, a%b); }   int main() {   int a = 50, b = 15;   int result = gcd(a, b);   printf("%d", result);   return 0; }