C++求最大公约数

C++ 求最大公约数（GCD）的方法详解

最大公约数（Greatest Common Divisor，GCD）是指能够整除两个或多个整数的最大正整数。以下是几种在C++中求最大公约数的方法：

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

这是最经典高效的求 GCD 算法，基于以下原理： \[ gcd(a, b) = gcd(b, a \% b) \]

#include <iostream>

// 递归实现
int gcd_recursive(int a, int b) 
{
    if (b == 0) return a;
    return gcd_recursive(b, a % b);
}

// 迭代实现
int gcd_iterative(int a, int b) 
{
    while (b != 0) 
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() 
{
    int num1, num2;
    std::cout << "请输入两个整数: ";
    std::cin >> num1 >> num2;
    
    std::cout << "递归法GCD: " << gcd_recursive(num1, num2) << std::endl;
    std::cout << "迭代法GCD: " << gcd_iterative(num1, num2) << std::endl;
    
    return 0;
}

2. 使用STL中的gcd函数（C++17及以上）

C++17在<numeric>头文件中提供了内置的gcd函数：

#include <iostream>
#include <numeric>

int main() 
{
    int num1, num2;
    std::cout << "请输入两个整数: ";
    std::cin >> num1 >> num2;
    
    std::cout << "STL内置GCD: " << std::gcd(num1, num2) << std::endl;
    
    return 0;
}