利用辗转相除法——求最大公约数

辗转相除法，也称欧几里德算法，可以用来求解两个整数的最大公约数（Greatest Common Divisor，简称GCD）。其基本思想是：用较大的数除以较小的数，再用余数（第一次除法的余数是较小数，以后每次的余数是上次的除数除以这次的余数）去除较小的数，直到余数为0为止，此时除数即为最大公约数。

以下是一个使用 Python 实现辗转相除法求解最大公约数的例子：

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

其中，a 和 b 是需要求解最大公约数的两个整数。函数首先判断 b 是否为 0，如果是则返回 a；否则进行辗转相除法的计算，将 b 与 a%b 的值赋给 a 和 b，直到 b 变为 0，此时 a 即为最大公约数。

相关问题

辗转相除法求最大公倍数c++

### 使用 C++ 实现辗转相除法计算最小公倍数

为了通过辗转相除法（也称为欧几里得算法）来求解两个整数的最大公约数并进一步得到它们的最小公倍数，在C++中的实现方式如下：

#### 定义函数用于求取最大公约数
定义一个名为`gcd`的函数，该函数接收两个参数作为待比较的正整数值，并返回这两个值之间的最大公约数。此过程利用了递归调用来不断缩小问题规模直到找到最终的结果。

int gcd(int m, int n) {
    if (n == 0)
        return m;
    else
        return gcd(n, m % n);
}

上述代码片段展示了如何采用递归形式编写最大公约数查找器[^2]。

#### 计算最小公倍数的方法
一旦获得了给定一对数字的最大公约数之后，则可以通过简单的乘法规则得出其对应的最小公倍数：即两数之积再除以其最大公约数即可获得结果。这里提供了一个辅助性的`lcm`函数来进行这项工作。

int lcm(int m, int n){
    return abs(m * n) / gcd(m, n); // 需要注意的是当处理负数情况时应考虑绝对值运算
}

这段程序说明了怎样基于之前提到过的最大公约数去构建一个新的表达式从而获取到所期望的小于等于任意指定范围内的所有自然数中能够被原始输入数据同时整除的那个最大的那个数。

#### 主函数部分
最后一步是在主函数内读入用户提供的成对整型变量并通过前面创建好的工具完成相应的逻辑操作后打印输出答案。

#include <iostream>
using namespace std;

// ... 上述已给出的 gcd 和 lcm 函数 ...

int main(){
    int num1, num2;
    
    cout << "请输入两个正整数：" ;
    cin >> num1 >> num2 ;

    cout << "\n最大公约数为：" << gcd(num1 ,num2 )<< endl;
    cout << "最小公倍数为：" << lcm(num1 ,num2)<< endl;

    return 0;
}

以上就是完整的源码列表，它实现了使用辗转相除法寻找两个特定整数间的关系——既包括两者间的最大公约数又涵盖了最小公倍数的概念。

辗转相除法求最大公约原理

### 辗转相除法（欧几里得算法）求解最大公约数的原理

#### 定义与基本概念
辗转相除法，也称为欧几里得算法，是一种用于计算两个正整数 \(a\) 和 \(b\) 的最大公约数的方法。该方法基于这样一个事实：两个数的最大公约数等于较小的那个数和两数之差的最大公约数。

对于任意两个非负整数 \(a\) 和 \(b\) （假设 \(a \geq b\)），如果 \(b=0\) 则 \(gcd(a,b)=a\)；否则有：

\[ gcd(a, b) = gcd(b, a \% b) \]

这里 `%` 表示取模运算符[^1]。

#### 数学解释
当给定一对整数 \(a\) 和 \(b\) 并且存在一个共同因数 \(d\) 使得 \(d|a\) 和 \(d|b\) 成立时，则必然满足 \(d|(a−⌊\frac{a}{b}⌋⋅b)\)[^4]。这意味着任何能够同时被 \(a\) 和 \(b\) 整除的数也可以被它们之间的线性组合所构成的新数值整除。这正是为什么可以通过重复应用上述性质来逐步简化问题直到找到最终的结果——即最大的公共因子为止的原因所在。

#### 接近过程的理解
此算法的核心在于它利用了余数的概念使我们逐渐接近目标值。每一次迭代都会减少其中一个参数直至达到终止条件 (\(b=0\)) 。在这个过程中，“单位份数”的概念帮助理解如何通过连续减去或调整较大的量使之更贴近另一个量从而实现两者间差距缩小的效果 [^2]。

def gcd_euclidean_algorithm(a, b):
    while b != 0:
        temp = b
        b = a % b
        a = temp
    
    return abs(a)

print(gcd_euclidean_algorithm(48, 18))