求最大公约数（最大公因数）—— 欧几里得算法

求最大公约数（最大公因数）—— 欧几里得算法

欧几里得算法，又称辗转相除法，是求解两个数最大公约数（GCD）的经典算法。这种方法通过不断用较小的数替换较大的数，并取余数，最终在余数为0时找到最大公约数。本文将详细介绍欧几里得算法的基本思想、具体步骤，并给出C++语言的迭代和递归实现方式。

欧几里得算法

欧几里得算法（又称辗转相除法）用于计算两个数的最大公因数，被称为是世界上最古老的算法。

基本思想

两个正整数 (a) 和 (b)，它们的最大公约数 (\text{gcd}(a,b)) 与 (b) 和 (a) 除以 (b) 得到的余数的最大公约数 (\text{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;
}

本文原文来自博客园