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

  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