欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  web前端

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)!