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

概述求两个正整数的最大公约数     思路：这是一个很基本的问题，最常见的就是两种方法，辗转相除法和辗转相减法。通式分别为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; } 

总结

以上是内存溢出为你收集整理的详解C语言求两个数的最大公约数及最小公倍数的方法全部内容，希望文章能够帮你解决详解C语言求两个数的最大公约数及最小公倍数的方法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。