C++求两个整数的最大公约数(GCD)方法

在C++中，计算两个整数的最大公约数(GCD)有多种方法，下面我将介绍几种常见的方法及其实现。

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

这是最经典且高效的GCD计算方法，基于以下数学原理：

gcd(a, b) = gcd(b, a % b)

迭代实现

int gcd_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

递归实现

int gcd_recursive(int a, int b) {
    if (b == 0) return a;
    return gcd_recursive(b, a % b);
}

2. 更相减损术

这是中国古代的算法，原理是：

gcd(a, b) = gcd(a-b, b) （当a > b时）

实现代码

int gcd_subtraction(int a, int b) {
    while (a != b) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }
    return a;
}

3. 使用STL中的gcd函数

C++17标准在
""头文件中提供了
"std::gcd"函数：

#include <numeric>
#include <iostream>

int main() {
    int a = 56, b = 98;
    std::cout << "GCD is " << std::gcd(a, b) << std::endl;
    return 0;
}

4. 二进制GCD算法（Stein算法）

这是一种更高效的算法，特别适合计算机实现，避免了耗时的取模运算：

int gcd_binary(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    
    int shift = 0;
    while (((a | b) & 1) == 0) {
        a >>= 1;
        b >>= 1;
        ++shift;
    }
    
    while ((a & 1) == 0) {
        a >>= 1;
    }
    
    do {
        while ((b & 1) == 0) {
            b >>= 1;
        }
        if (a > b) {
            std::swap(a, b);
        }
        b -= a;
    } while (b != 0);
    
    return a << shift;
}

性能比较

1. 欧几里得算法（辗转相除法）通常是最快的，特别是对于大数
2. 更相减损术在大数情况下效率较低
3. 二进制GCD算法避免了取模运算，在某些平台上可能更快

完整示例

#include <iostream>
#include <numeric> // 用于std::gcd

// 辗转相除法（迭代）
int gcd_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 辗转相除法（递归）
int gcd_recursive(int a, int b) {
    return b == 0 ? a : gcd_recursive(b, a % b);
}

// 更相减损术
int gcd_subtraction(int a, int b) {
    while (a != b) {
        if (a > b) a -= b;
        else b -= a;
    }
    return a;
}

// 二进制GCD算法
int gcd_binary(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    
    int shift = 0;
    while (((a | b) & 1) == 0) {
        a >>= 1;
        b >>= 1;
        ++shift;
    }
    
    while ((a & 1) == 0) a >>= 1;
    
    do {
        while ((b & 1) == 0) b >>= 1;
        if (a > b) std::swap(a, b);
        b -= a;
    } while (b != 0);
    
    return a << shift;
}

int main() {
    int a = 56, b = 98;
    
    std::cout << "Numbers: " << a << ", " << b << std::endl;
    std::cout << "GCD (iterative): " << gcd_iterative(a, b) << std::endl;
    std::cout << "GCD (recursive): " << gcd_recursive(a, b) << std::endl;
    std::cout << "GCD (subtraction): " << gcd_subtraction(a, b) << std::endl;
    std::cout << "GCD (binary): " << gcd_binary(a, b) << std::endl;
    
    // C++17标准方法
    #if __cplusplus >= 201703L
    std::cout << "GCD (std::gcd): " << std::gcd(a, b) << std::endl;
    #endif
    
    return 0;
}

在实际应用中，推荐使用欧几里得算法（辗转相除法）或C++17的
"std::gcd"函数，因为它们既高效又简洁。