欧几里得算法

定义

欧几里得算法用于求两个正整数的最大公因数,其内容为:设\(\gcd(a,b)\)为正整数\(a,b\)的最大公因数,则\(\gcd(a,b)=\gcd(b,a \bmod b)\)

求解算法

思路与简单证明

不妨设\(\gcd(a,b)=c,a>b,\lfloor \frac ab\rfloor=k,a \bmod b=r\)

\(a=mc,b=nc\),易得\(\gcd(m,n)=1\)

代入得\(r=a-bk=mc-nck=(m-nk)c\)

若要证\(\gcd(a,b)=\gcd(b,r)=c\),就要证\(\gcd(n,m-nk)=1\)

假设\(\gcd(n,m-nk)=d\neq 1\)

\(n=xd,m-nk=yd\)

代入得\(m=ydk+xd=(x+yk)d\)

\(\gcd(n,m)=d\neq 1\),与\(\gcd(n,m)=1\)矛盾,故假设不成立,即\(\gcd(n,m-nk)=1\),故得证;

于是我们可以递归实现,边界条件:设在第\(k\)层递归\(b_k=0\),即第\(k-1\)层递归\(a_{k-1} \bmod b_{k-1}=0\)时,可得\(a_{k-1}\)\(b_{k-1}\)的倍数,即\(\gcd(a_{k-1},b_{k-1})=b_{k-1}\),得出\(\gcd(a_1,b_1)=b_{k-1}\)

故可在第\(k\)层递归返回\(a_k\),终止递归。

实现

1
2
3
4
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
作者

xqmmcqs

发布于

2017-11-07

更新于

2021-03-06

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×