欧几里得算法：求解最大公约数的古老智慧

欧几里得算法：求解最大公约数的古老智慧

欧几里得算法，又称辗转相除法，是求两个数最大公约数（GCD）的高效算法。这种方法避免了因式分解的复杂性，特别适用于处理大数。本文将详细介绍欧几里得算法的基本原理、具体步骤，并提供C++语言的迭代和递归实现代码。

欧几里得算法简介

欧几里得算法（又称辗转相除法）用于计算两个数的最大公因数，被称为是世界上最古老的算法。其基本思想是：两个正整数a和b，它们的最大公约数（gcd(a,b)）与b和a除以b得到的余数的最大公约数（gcd(b,a%b)）相同。通过不断用较小的数替换较大的数，并取余数，最终在余数为0时找到最大公约数。

举例说明

以求1112与695这两个数的最大公约数为例：

• 首先用较大的数字除以较小的数字，求出余数，也就是堆两个数字进行模运算。得到余数417
• 接下来再用除数695和余数417进行模运算，结果为278。
• 继续进行同样的操作，对417和278作模运算，结果为139。
• 对278和139作模运算，结果为0，也就是说278可以被139整除。
• 余数为0时，最后一次运算中的除数139就是1112和695的最大公约数。

算法实现

以下是欧几里得算法的C++代码实现，包括迭代和递归两种方式：

#include "iostream"
using namespace std;

/*欧几里得算法—求最大公约数—迭代实现*/
int gcd(int a, int b){
    while (b != 0){
        int tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

/*欧几里得算法—求最大公约数—递归实现*/
int gcd_dg(int a, int b){
    return b == 0 ? a : gcd_dg(b, a % b);
}

int main(){
    cout << gcd(1112, 695) << endl;
    cout << gcd_dg(1112, 695) << endl;
    system("pause");
    return 0;
}

通过以上代码，我们可以看到迭代和递归两种实现方式都能正确计算出两个数的最大公约数。这种方法不仅简单易懂，而且在处理大数时效率远高于因式分解法。