JavaScript趣题:分解质因数
程序员文章站
2022-06-04 20:33:55
...
把一个正整数分解成若干个质数因子的过程称为分解质因数。
举个简单的例子:
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 }
以上就是JavaScript趣题:分解质因数的内容,更多相关内容请关注PHP中文网(www.php.cn)!
上一篇: 21个常用的PHP函数代码段
下一篇: 怎么将数据库信息用php存入数组当中