C++最小公约数重写

Question

我创建了一个返回2个数字的最小公约数的函数.

int check (int a, int b)
{
 int i = 2; //every number is divisible by 1
   begin:
    if ((a % i == 0) && (b%i == 0)) //i must be divisible by both numbers
      {
         return i;
      }
    else
      {
          i++;
          goto begin;
      }
}

但是,我正在使用备受建议的反对goto,所以我想知道如何使用for或while循环重写它.

Answer 1

如果a和b是共素(gcd = 1),则只有在溢出并达到-1时,您的算法才会终止.即经过40亿次迭代.

即使不是这种情况,你的算法也很慢(gcd中的线性(a,b)).你应该研究更快的欧几里德算法.

您的代码处于重写形式(终止问题未修复),因此它等同于您的旧代码:

int check (int a, int b)
{
 int i = 2; //every number is divisible by 1
   while(!((a % i == 0) && (b%i == 0)))//i must be divisible by both numbers
   {
      i++;
   } 
   return i;
}

重写为一个for循环,一旦明确gcd == 1就终止

int check (int a, int b)
{
  for(int i=2;i<=Math.Min(a,b);i++)
  {
    if((a % i == 0) && (b%i == 0))
      return i;
  }
  return 1;
}