首页 > 其他 > 详细

Fcc找出能被给定的两个参数和参数之间所有连续数字整除的最小公倍数。

时间:2017-01-25 12:31:31      阅读:184      评论:0      收藏:0      [点我收藏+]

原题代码如下:

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找出能被给定的两个参数和参数之间所有连续数字整除的最小公倍数。

原文:http://www.cnblogs.com/oldchicken/p/6349282.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!