首頁 > web前端 > js教程 > JavaScript趣題:分解質因數

JavaScript趣題:分解質因數

黄舟
發布: 2017-01-22 14:44:13
原創
2753 人瀏覽過

把一個正整數分解成若干個質數因子的過程稱為分解質因數。

舉個簡單的例子:

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 // { &#39;2&#39;: 3, &#39;3&#39;: 1 }
登入後複製

以上就是JavaScript趣題:分解質因數的內容,更多相關內容請關注PHP中文網(www.php.cn)!

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板