算法-辗转相除法

2026年09月24日 04:10

有1个网友回答

网友（1）：

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

对于两个数的最大公约数的求解，在我们的笔算过程中，通常是使用一个短除法，本质上其实也就是进行一个质因数分解的过程，但对于一个较大的数来说，将其进行质因数分解是一件非常耗时的过程，这显然不是一个好的做法，因此基于数论基础，我们有了辗转相除法，也叫做欧几里得算法。

在叙述该算法之前，先了解辗转相除法的实现前提也就是GCD递归定理：

基于上面的GCD递归定理，我们便可以知道可以采用递归的方式，对两个整数的最大公约数进行相对较为高效的计算。

下面我们采用递归方式实现辗转相除法。
(以下引用自《算法导论》)

GCD(a, b)