首页 > 代码库 > Fcc找出能被给定的两个参数和参数之间所有连续数字整除的最小公倍数。
Fcc找出能被给定的两个参数和参数之间所有连续数字整除的最小公倍数。
原题代码如下:
function smallestCommons(arr) { return arr; } smallestCommons([1,5]);
最小公倍数的参考资料:https://www.mathsisfun.com/least-common-multiple.html。
因为参数不一定是从小到大排序的,所以需要先对参数做一个排序:
arr=arr.sort();
然后需要了解到的是如何求最小公倍数, 通过查询资料了解到最小公倍数的求法,A,B两个数的最小公倍数公式:A*B/gcd(A,B的最大公约数)。
有了这个算法,只需要要对连续数字头两个进行求最小公倍数,然后再把这个值和下一个数字求最小公倍数,遍历到最大参数即可。
var num=arr[0]; for(var i=arr[0]+1;i<=arr[1];i++){ num*=i/gcd(i,num); }
现在我们还缺的是如何求最大公约数, 需要使用的公式是欧几里德定律。
function gcd(m,n){ if(m%n===0){ return n; } return gcd(n,m%n); }
完整代码如下:
function smallestCommons(arr) { arr=arr.sort(); var num=arr[0]; for(var i=arr[0]+1;i<=arr[1];i++){ num*=i/gcd(i,num); } return num; } function gcd(m,n){ if(m%n===0)return n; return gcd(n,m%n); } smallestCommons([1,5]);
Fcc找出能被给定的两个参数和参数之间所有连续数字整除的最小公倍数。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。