js实现将一个正整数分解质因数

更新日期: 2018-09-25阅读量: 6639标签: 算法

js 把一个正整数分解成若干个质数因子的过程称为分解质因数。  举个简单的例子: 

24分解质因数为2*2*2*3,简写成(2^3) * (3^1)。 


 在计算机方面,我们可以用一个哈希表来存储这个结果,在js中可以用如下的形式表示: { '2': 3, '3': 1 } ,那么如何分解质因数呢? 


 首先,你需要一个判断是否为质数的方法:

function isPrime(n){
    for(var i=2;i<=Math.sqrt(n);i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}


然后,利用短除法来分解:

function PrimeFactorizer(n){
	//用来存储结果的hash
    var hash = {};
    while(n > 1){
		//从最小的质数开始除
        for(var i=2;i<=n;i++){
            if(isPrime(i) && n % i == 0){
				//如果hash中有这个质数,则存储的数目+1
                if(hash[i]){
                    hash[i] = hash[i] + 1;
                }//否则把该质数作为key,value为1
                else{
                    hash[i] = 1;
                }
				//除掉这个最小的质数因子
                n /= i;
            }
        }
    }
	//给实例上加个factor属性
    this.factor = hash;
    hash = null;
}
 
new PrimeFactorizer(24).factor // { '2': 3, '3': 1 }


站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

链接: https://www.fly63.com/article/detial/1112

JS算法之深度优先遍历(DFS)和广度优先遍历(BFS)

在开发页面的时候,我们有时候会遇到这种需求:在页面某个dom节点中遍历,找到目标dom节点,我们正常做法是利用选择器document.getElementById(),document.getElementsByName()或者document.getElementsByTagName(),

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

js算法-查找斐波纳契数列中第N个数

所谓的斐波纳契数列是指前2个数是 0 和 1 ,第 i 个数是第 i-1 个数和第i-2 个数的和。下面我们来用js获取菲波那契数列的第N个数为多少:递归、闭包+缓存、直接计算出该数列的值得数组,然后再从数组中取值 、直接使用数学表达式

JS数据结构与算法_树

一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点:关于数的深度和高度的问题,不同的教材有不同的说法

JavaScript 实现归并排序

在本文中,我们学习 Merge Sort 背后的逻辑,并用 JavaScript 实现。最后,在空间和时间复杂度方面将归并排序与其他算法进行比较。

JavaScript数据结构与算法-String

给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。主要就是用到了数组的 split 、 reverse 、 join 、 map 方法,原理:就是把字符串变成数组

Js实现插入排序

插入排序是一种非常简单的算法,最适合大部分已经被排好序的数据。在开始之前,通过可视化演示算法如何运作一个好主意。你可以参考前面的动画来了解插入排序的工作原理。

不懂算法,还想进大厂?做梦吧

学算法,刷题蛮干是不行的,需要遵循科学的方法。以下的经验技巧,对于算法新手,或大学没有搞过ACM,想利用业余时间提升算法能力的同学比较有帮助,对于算法高手和ACM大牛

从js讲解时间复杂度和空间复杂度

今天有同事在检查代码的时候,由于函数写的性能不是很好,被打回去重构了,细思极恐,今天和大家分享一篇用js讲解的时间复杂度和空间复杂度的博客;复杂度的表示方式之前有看过的,你可能会看到这么一串东西

用 JavaScript 实现链表

单链表是表示一系列节点的数据结构,其中每个节点指向链表中的下一个节点。 相反,双向链表具有指向其前后元素的节点。与数组不同,链表不提供对链表表中特定索引访问。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!