详解C语言求两个数的最大公约数及最小公倍数的方法

发布时间：2020-12-16 05:33:27 所属栏目：百科来源：网络整理

导读：求两个正整数的最大公约数思路：这是一个很基本的问题，最常见的就是两种方法，辗转相除法和辗转相减法。通式分别为 f(x,y) = f(y,x%y),f(x,x - y) (x =y 0)。根据通式写出算法不难，这里就不给出了。这里给出《编程之美》上的算法，主要是为了减少迭代的次

求两个正整数的最大公约数

思路：这是一个很基本的问题，最常见的就是两种方法，辗转相除法和辗转相减法。通式分别为 f(x,y) = f(y,x%y),f(x,x - y) (x >=y > 0)。根据通式写出算法不难，这里就不给出了。这里给出《编程之美》上的算法，主要是为了减少迭代的次数。
对于x和y，如果y = k * y1,x= k * x1，那么f(x,y) = k * f(x1,y1)。另外，如果x = p * x1，假设p为素数，并且y % p != 0，那么f(x,y) = f(p * x1,y) = f(x1,y)。取p = 2。

参考代码：

//函数功能: 求最大公约数 
//函数参数: x,y为两个数 
//返回值:  最大公约数 
int gcd_solution1(int x,int y) 
{ 
  if(y == 0) 
    return x; 
  else if(x < y) 
    return gcd_solution1(y,x); 
  else 
  { 
    if(x&1) //x是奇数 
    { 
      if(y&1) //y是奇数 
        return gcd_solution1(y,x-y); 
      else  //y是偶数 
        return gcd_solution1(x,y>>1); 
    } 
    else //x是偶数 
    { 
      if(y&1) //y是奇数 
        return gcd_solution1(x>>1,y); 
      else  //y是偶数 
        return gcd_solution1(x>>1,y>>1) << 1; 
    } 
  } 
}

求最小公倍数：
最常用的是辗转相除法，有两整数a和b：
① a%b得余数c
② 若c=0，则b即为两数的最大公约数
③ 若c≠0，则a=b，b=c，再回去执行①

下面非递归版本：

int gcd_solution2(int x,int y) 
{ 
  int result = 1; 
  while(y) 
  { 
    int t = x; 
    if(x&1) 
    { 
      if(y&1) 
      { 
        x = y; 
        y = t % y; 
      } 
      else 
        y >>= 1; 
    } 
    else 
    { 
      if(y&1) 
        x >>= 1; 
      else 
      { 
        x >>= 1; 
        y >>= 1; 
        result <<= 1; 
      } 
    } 
  } 
  return result * x; 
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!