首页 > 代码库 > 最大公约数与欧几里得(Euclid)算法
最大公约数与欧几里得(Euclid)算法
---恢复内容开始---
记a, b的最大公约数为gcd(a, b)。显然, gcd(a,b)=gcd(|a|,|b|).
计算最大公约数的Euclid算法基于下面定理:
【GCD递归定理】对于任意非负整数a和任意正整数b,gcd(a,b)=gcd(b,a%b)。
=============================================================
gcd(a,b)=gcd(b, a+kb) a,b,k为任意整数
即gcd(a,b)=gcd(b, a mod b) a≥0,b>0
Example:gcd(55,22)=gcd(22, 55mod22)=gcd(22,11)=11
证明:假定d=gcd(a,b),那么有d|a和d|b.对任何正整数b,a可表示为如下形式: a=kb+r ≡r mod b, a mod b =r , 因此,有(a mod b)= a-kb,k为某个整数。但由于d|b,b也能整除kb, 而d|a,故有d|(a mod b), 这表明d 也是b 和(amod b) 的公因子。由于这是可逆的,如果d 是b 和(a mod b) 的公因子,那么d|kb,且d|[kb+(a mod b)],这等同于d|a。这样a和b的公因子集合等同于b 和(a mod b) 的公因子集合。
==============================================================
Euclid算法最简单的递归版本如下:
1 int Euclid(int a,int b)2 {3 b == 0 ? return a : Enclid(b, a%b);4 }
迭代版本:
---恢复内容结束---
最大公约数与欧几里得(Euclid)算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。