最大公因数（GCD）

最大公因数是指两个或多个整数的所有公因数中最大的一个。对于两个整数 $a$ 和 $b$，它的最大公因数通常记作 GCD(a,b) 或 gcd(a,b)。

计算方法：

1. 列举法：列出两个数的所有因数，然后找出它们的公因数，最后选出其中最大的一个。

2. 辗转相除法（欧几里得算法）：

• 将较大的数除以较小的数，得到余数。

• 用较小的数除以这个余数，再得到新的余数。

• 重复上述步骤，直到余数为0。此时，最后一个非零余数即为最大公因数。

例如，求 GCD(48,18)：

48÷18=2 余 12

18÷12=1 余 6

12÷6=2 余 0

所以， $=6$。

#include <iostream>

// 计算最大公因数（欧几里得算法）
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int a = 48;
    int b = 18;

    std::cout << "GCD of " << a << " and " << b << " is: " << gcd(a, b) << std::endl;
    

    return 0;
}

• 使用欧几里得算法来计算最大公因数。该算法的核心思想是通过不断取余，直到余数为0，最后一个非零的余数就是最大公因数。

• gcd 函数通过循环不断更新 a 和 b 的值，直到 b 为0。