javascript来计算最大公约数和最小公倍数

javascript来计算最大公约数和最小公倍数

月光魔力鸭

2018-10-15 17:58 阅读 1206 喜欢 2 最大公约数 最小公倍数

最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法更相减损法。与最大公约数相对应的概念是最小公倍数,a,b的最小公倍数记为[a,b]。

以上为概念,为什么讲这个问题呢?请看这里...codewars-js-刷题

下面只说几个常用的实现思路:

普通轮询

function gcd(a,b){
    var div = 1,max = Math.max(a,b),min = Math.min(a,b);
    for(let i=1;i<min;i++){
        if(max % i === 0 && min % i === 0){
            div = i;
        }
    }
    return div;
}

我们通过遍历最终获得一个最大的公约数。当然遍历顺序也可以反过来,这样步骤会相对少一部分的。

function gcd(a,b){
    var div = 1,max = Math.max(a,b),min = Math.min(a,b);
    for(let i=min;i>=1;i--){
        if(max % i === 0 && min % i === 0){
            div = i;
            break;
        }
    }
    return div;
}

辗转相除法

function gcd(a,b){
  if(b === 0)return a;
  return gcd(b,a % b);
}

通过相除然后递归获得最终的最大公约数,当然也可以简写..

const gcd= (a, b) => b ? gcd(b, a % b) : a;

辗转相减法

function gcd(a,b){
    var p = Math.abs(a - b ),min = Math.min(a,b);
    if(min % p === 0)return p;
    return gcd(min,p);
}

以上三种方式可以通过js来获得两个数的最大公约数。当我们有了最大公约数后,就可以通过最大公约数获得两个数的最小公倍数。

[a,b] = a * b / (a,b)
a 与 b的最小公倍数等于 a与b的乘积 除以 a与 b的最大公约数。

最小公倍数

const gcd = (a, b) => b ? gcd(b, a % b) : a;//获得ab 的最大公约数
const lcm = (a, b) => a * b / gcd(a, b);//获得ab的最小公倍数

顺便,这里再贴下关于这道题的解法:

const gcd = (a, b) => b ? gcd(b, a % b) : a;
const lcm = (a, b) => a * b / gcd(a, b);

function convertFrac(arr) {
  const cd = arr.reduce((a, [_, d]) => lcm(d, a), 1);
  return arr.map(([n, d]) => `(${n * cd/d},${cd})`).join('');
}
//声明下,这个解法并不是我的。

以上为通过js来计算两个数的最大公约数和最小公倍数的实现方式。

转载请注明出处: https://chrunlee.cn/article/js-common-denominators.html


感谢支持!

赞赏支持
提交评论
评论信息 (请文明评论)
暂无评论,快来快来写想法...
推荐
最近一直在想着抓一些网盘数据,进行资料归拢,可是当我真正开始的时候.. 还是遇到了反爬,当然我本身就有心理预期,这是肯定会碰到的,只是没想到会在代理IP上耗费这么久,之前的时候也处理过代理IP ,可是由于一知半解,导致很多配置都不理解,debug全靠猜...
本文概括了递归、闭包、原型、继承,理清这些基本的概念,有助于你接纳更多的东西,我们会在下一个章节对函数进行更深入的讨论。
问题是由一个BUG引起的,功能中有使用国际化组件,用的是jquery.i18n,在chrome上、ff上都没有什么问题,问题出在了IE上。万恶的IE..
web网站上总会有在文本域中提交代码的操作,那么如何处理呢?
关于jquery,他的核心特点就是无new构造和链式调用,这里根据网上的资料,自己简单理解下,有助于消化核心代码。
web开发中,前台有时候会需要一个随机数或序列,通常来说,这个随机数可能只在当前页面中使用,并不需要太过严格,大体上重复率低即可。
我们有时候会拿textarea来做编辑器,但是常用编辑器都是支持tab缩进的,这里对textarea监听下事件处理下即可实现。
jsQR 是一款纯粹的由javascript实现的二维码识别库,可以在浏览器端使用,也可以在后端node.js环境使用。我之前使用过其他的识别库,例如:qrcode-reader 或其他,在使用上都比较麻烦,而且识别率并不高。jsQR是后来发现的,感觉(没有实际对比验证)jsQR识别率要更高些,使用起来也更简单,不需要安装其他依赖软件。