JavaScript趣题：分解质因数

举个简单的例子：

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 }