首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

求N个数据的最贵族约数和最小公倍数

2013-08-16 
求N个数据的最大公约数和最小公倍数gcd: greatest common divisor最大公约数lcm: least common multiplier

求N个数据的最大公约数和最小公倍数
gcd: greatest common divisor  最大公约数
lcm: least common multiplier  最小公倍数

如果是N=2的话,
求gcd:
loop:
if a > b:
   temp = a % b
   if temp == 0: 
       gcd = b
   a = b
   b = temp
else:
    ...

求lcm的话就是 a * b / gcd

当 N > 2时,需要递归,先求前2个数的gcd & lcm,然后把它和第3个再进行求,第4个...

数学分析,首先找出各个数的全部因子,gcd就是取这些因子中的公共部分,lcm就是因子的并集。
以8 10 12三个数分析:
8 = 2 * 2 * 2
10 = 2 * 5
12 = 2 * 2 * 3
gcd就是2, lcm就是2 * 2 * 2 * 5 * 3

求一个数的所有因子见我的另一篇blog。

热点排行