求最大公约数gcd
使用辗转相除法和更相减损法求最大公约数
github快速求两个数的最大公约数(公因数)有两个办法:
- 更相减损法
- 辗转相除法
更相减损法
原理:两个正整数a和b(a>b),它们的最大公约数等于a-b(大减小)和b(小)的最大公约数。
int gcd(int a,int b) {
if(a==b) return a;
if(a>b) return gcd(a-b,b);
if(a<b) return gcd(b-a,a);
}
辗转相除法
原理:两个正整数a和b(a>b),它们的最大公约数等于a%b(大模小)和b(小)之间的最大公约数。
why?
- 假设最大公约数是x, 显然,x也是a%b因数。
- 现在证明x是a%b和b的最大公因数:假设存在更大的公因数y,因为a=kb+a%b, 则y肯定也是a的公因数。因此x=y,得证。
int gcd(int a,int b) {
if(b==0) return a;
else return gcd(b,a%b);
}
// 一行写法
int gcd(int a,int b) {
return b ? gcd(b,a%b):a;
}
比较
更相减损法避免了大整数取模导致效率低下的问题,但是运算次数要比辗转相除多得多。
Reference
- https://www.cnblogs.com/fusiwei/p/11301436.html