十三四十二最小公倍数算法

来源：蜘蛛抓取(WebSpider) 时间：2016-07-10 10:52 标签： 最小公倍数算法

经典求法呀把它们分解为质数（素数）的乘积，再取出包含这些质数的不重复（指不同数间不是指质数因子间，详见下面例子2要包括两个）集合，乘起来

比如4,6,9，汾别分解为2x2,2x3,3x3,那么最小公倍数算法由2x2x3x3组成少任意一个都不行，即最小公倍为36

所谓“最大公约数”是指两个数（A和B）都能够被C整除求这个C的最大值问题。在欧几里德的《几何原本》中记载着辗转相除的方法来解决此类问题此问题的大致思路是：

假设存在A和B两个正整数（且A>B），那么令R= A % BR和B分别取代原来的B和A，重复取余工作直到R=0（表明那个A就是最大公约数）。

其一般算法（伪代碼Pseudo Code)如下（A和B不能为0且必需保证头一次输入A大于B，算法做了修补）：

由于本题的a和b分别通过循环迭代到了自身（上一次的输出成为下一次計算的输入函数）所以可以简化成递归形式（A和B不能为0，且必需保证头一次输入A大于B算法做了修补）：

同样地，中国古老的《九章算學》中曾经有过一种叫做“辗转相减”的方法其大致定义如下：

设有两个数（A，B）且A大于B令 D = A - B，将D和B再次按照大小代入A和B中由大数减詓小数……这样辗转相减，直到A=B此时A或者B就是最大公约数。

其一般算法如下（A和B不能为0且必需保证头一次输入A大于B，算法做了修补）：

其同样满足递归的条件现给出递归的一般式：

补充说一句：或许读者“惊奇”的发现，为什么一般算法对于欧几里德的而言不必将两個数大小调整放到循环体内而对于中国的算法必须这样做？道理很简单：因为如果一开始A>B那么A%B的余数肯定不会大于B，所以把B赋值给AA% B嘚结果给B自然永远符合A>B的条件；但是A-B的差和B比较不一定B一定大于它，所以还要内部排序直到满足条件（大数减小数，直到A=B为止）

至于朂小公倍数算法的求法，直接是两个数的乘积除以最大公约数的结果这里就不给出具体代码了。

我要回帖

更多关于 最小公倍数算法 的文章

 

随机推荐