这里主要要介绍的欧几里得算法,主要是用于求解两个整数的最大公约数的问题。
传统的求解方法是采用暴力枚举的方法,即枚举所有可能值取其最大。其算法描述如下:
给定两个整数a,b
c = min{a, b}
max = 0; // 保存最大公约数
for i:0->c
if (a % i == 0) And (b % i == 0) // '%'表示取模运算
if (max < i)
max = i;
return max;
显然,暴力破解所花费的时间会随着两个整数的增大而上升,尤其是当超过10000000后,求解速度就不是很理想了。
接下来介绍的欧几里得算法可用于简化该问题求解的规模。
假设
是两个整数
和
的公约数,即存在整数
和
,使得下列式成立
不妨假设 ,则有如下成立:
其中 ,即 是 除 的余数
将 (1) 代入 (2) 可得:
即 可以整除
通过(1)、(2)、(3)可知, 同时是 的公约数
那么,求解
的最大公约数,是不是等价于求解
的最大公约数呢?
接下来证明这个命题:
假设
是
的最大公约数,而
的最大公约数为
,其中
,即
将(4)代入(2)
即
由(5)可知, 也是 的公约数。但之前假设 是 的最大公约数,而 ,所以这与条件相矛盾。故说明 求解 的最大公约数等价于求解 的最大公约数。
通过欧几里得算法,可以将求解 的最大公约数转化为求解 的最大公约数。注意到,该过程是可以重复的。其伪代码如下:
给定两个整数a,b // 假设 a > b > 0
while (r == 0) {
r = a % b;
a = b;
b = r;
}
return a;