【信息科学与工程学】计算机科学与自动化——第三篇 计算理论基础05 计算数论01

欧几里得算法

通过辗转相除，利用余数逐步缩小问题规模

基于等式gcd(a,b)=gcd(b,a mod b)的递归关系

gcd(a,b)=gcd(b,a mod b)

递归：
1. 如果b=0，返回a
2. 否则返回gcd(b,a mod b)

确定性，简单高效，无需质因数分解

O(log min(a,b))

O(log min(a,b))（递归栈）或O(1)（迭代）

整数最大公约数计算