求最大公约数gcd

快速求两个数的最大公约数(公因数)有两个办法：

1. 更相减损法
2. 辗转相除法

更相减损法

原理：两个正整数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