c++ - 2 个数的公因数是多少？

Question

通常我们会发现两个数字之间的公因数，例如 8 和 12 为 4。 但是在编程语言中，我想找到两个数都除以 2 时的公共(public)数。 我们将两个数字除以 2 并检查公共(public)数字 比如数字 8 和 11 8->4->2 11->5->2 她的我们得到2作为公共(public)号码。 我想为 10^9 以下的数字有效地实现它。 她的是我的实现

long long i,j;
while(i!=1||j!=1)
{
    i=i/2;
    j=j/2;
    if(i==j)
    flag=1;
    break;
}

但 i 和 j 在不同时间会相同。如何实现？

Answer 1

你可以用更复杂的逻辑来做到这一点——使用两个数字并始终除掉其中较大的一个:

int get(int a, int b) {
  while (a != b) {
    if (a < b) {
      swap(a, b);
    }
    a /= 2;
  }
  return a;
}

解释:最终任何正整数除以 2 都会得到 1，因此循环肯定会终止，最坏的情况是 a 和 b 都是1. 在每一步中，我都确保 a 不小于 b，然后将其除以 2。