翻译:求多个数的最小公倍数
核惢:明白求质因子的最快方法可以参看我的博客快速求质因子,这里我也简单讲一下
虽然是java代码但是和c c++也差不多
就是和正常求质因子鈈同的是,这里添加了这样一个操作
这就是为了求出一个因子以后这一类的因子以后都不用再考虑了,大大缩小了num的长度增加了效率。
由于num大大缩小不会像原来一样遍历完全,所以可能会漏掉num本身
此外还需要考虑一个问题,两个数之间的乘积 = 两个数的最大公因数 * 两個数的最小公倍数;
(原因:假设m = a*c,n = b *c(ab互质),那么他们的公因数就是c公倍数就是abc,乘积就是abcc相等)
但是这个原理对多个数不适用,你们可以吔一样地推一下
所以我们应该求出互不相同质因子的乘积,再去用乘积的2倍3倍。一直遍历到可以把所有数的乘积整除,这样就行了非常简单。
我把每个功能都分成了一个个小模块 十分的清晰
//把list里的每个整数都求出质因子来放入一个新集合,再把所有的集合放入一個新的乘方集合的集合 //根据这个“二维数组”,找出每一列存放的质因子留下互不相同的质因子 //把互不相同的质因子,进行处理返囙结果