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

时间: 2018-09-25阅读: 152标签: 算法

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 }


js实现合并两个有序数组

给定两个有序整数数组arr1和arr2,将 arr2和arr1进行合并为一个单调非递减的数组,并将其输出。方法一利用循环、方法二直接使用数组的sort方法。

js算法实现_二维数组中的查找

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数

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

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

js求水仙花数_JavaScript可自定义范围打印水仙花数

水仙花数是指一个 n 位正整数 ( n≥3 ),它的每个位上的数字的 n 次幂之和等于它本身(例如:1^3 + 5^3+ 3^3 = 153)。这篇文章主要介绍js实现生成自定义范围内的水仙花数。

js实现生成任意长度的随机字符串

js生成任意长度的随机字符串,包含:数字,字母,特殊字符。实现原理:可以手动指定字符库及随机字符长度,利用Math.round()和Math.random()两个方法实现获取随机字符

js求数组中的最大差值的方法总汇

有一个无序整型数组,如何求出这个数组中最大差值。(例如:无序数组1, 3, 63, 44最大差值是 63-1=62)。实现原理:遍历一次数组,找到最大值和最小值,返回差值

js实现统计一个字符串中出现最多的字母的方法总汇

给出一个字符串,统计出现次数最多的字母。方法一为 String.prototype.charAt:先遍历字符串中所有字母,统计字母以及对应显示的次数,最后是进行比较获取次数最大的字母。方法二 String.prototype.split:逻辑和方法一相同,只不过是通过 split 直接把字符串先拆成数组。

js之反转整数算法

将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。

js算法_js判断一个字符串是否是回文字符串

什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a

PageRank算法的定义与来源、以及PageRank算法原理

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。