详解C语言求两个数的最大公约数及最小公倍数的方法
更新时间:2020年4月25日 17:35 点击:1543
求两个正整数的最大公约数
思路:这是一个很基本的问题,最常见的就是两种方法,辗转相除法和辗转相减法。通式分别为 f(x, y) = f(y, x%y), f(x, y) = f(y, 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语言辗转相除法求2个数的最小公约数,非常不错,感兴趣的朋友一起看看吧...2020-04-25
- 这篇文章主要介绍了C++ 实现多数的最大公约数的实例的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了c++ 实现求最大公约数和最小公倍数的相关资料,需要的朋友可以参考下...2020-04-25
- 本文介绍了使用C#获取两个数的最大公约数和最小公倍数的示例,大家参考使用吧...2020-06-25
- 今天整理了一下用递归法求最大公约数(gcd)和最小公倍数(lcm)。主要的工作是求最大公约数。数学上可以用辗转法求最大公约数...2020-04-25
- 这篇文章主要介绍了C++求四个正整数最大公约数的方法,涉及C++求余算法的运用技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言求两个数的最大公约数及最小公倍数的方法,辗转相除法和辗转相减法在解决这种问题时最常用到,需要的朋友可以参考下...2020-04-25