gcd

递归求法：

//用的最多
int gcd(int a, int b)//快速算最大公因数
{
    return !b ? a : gcd(b, a % b);
}

迭代求法：

int gcd(int a, int b) {
  while (b != 0) {
    int tmp = a;
    a = b;
    b = tmp % b;
  }
  return a;
}

C++14 可用 __gcd (a, b)

大数的 gcd：

Big gcd(Big a, Big b) {
  // 记录a和b的公因数2出现次数
  int atimes = 0, btimes = 0;
  while (a % 2 == 0) {
    a >>= 1;
    atimes++;
  }
  while (b % 2 == 0) {
    b >>= 1;
    btimes++;
  }
  for (;;) {
    // a和b公因数中的2已经计算过了，后面不可能出现a,b均为偶数的情况
    while (a % 2 == 0) {
      a >>= 1;
    }
    while (b % 2 == 0) {
      b >>= 1;
    }
    if (a == b) break;
    // 确保 a>=b
    if (a < b) swap(a, b);
    a -= b;
  }
  return a << min(atimes, btimes);
}