Java分解整型質因數

前言

基本分解質因數法

素數分解質因數法

Matlab2014a版分解質因數法

後記

前言

        前面寫過兩篇關于素數相關的部落格，一篇是關于如何判斷素數，一篇是關于如何求取指定範圍的素數集。參考百度百科，分解質因數就是是把一個合數分解成若幹個質因數的乘積形式。可以看到分解質因數其實和質數還是關系的，是以萌發了寫這篇部落格的念頭。

基本分解質因數法

        該方法的基本思想就是找到分解後的質數，通過求餘疊代實作。我在網上找到一個介紹該算法思路比較通俗的博文，傳送門：分解質因數算法。代碼如下：

public static int[] factor(int n){
    if(n < 0){
        throw new IllegalArgumentException("N must be a non negative integer.");
    }
    if(n < 4){
        return new int[]{n};
    }
    int factorNums = (int)(Math.log(Integer.highestOneBit(n)) / Math.log(2));
    int[] factors = new int[factorNums];
    int factorCount = 0;
    for(int i = 2; i <= (int) Math.sqrt(n); i++){
        if(n % i == 0){
            factors[factorCount++] = i;
            n /= i;
            i = 1;
        }
    }
    factors[factorCount++] = n;
    return Arrays.copyOf(factors, factorCount);
}
           

        原理比較簡單，具體參照我給的傳送門。我主要說說那個factorNums值，它是個估計質因子數量的值。我們知道2是最小質數，是以如果一個數的質因子全是2，那麼所有比它小的數，它們的質因子數一定會比它少。并且如果一個資料n在

和

之間，那麼它的質因數的長度絕對小于等于m，反證法很好證明，這裡就不多說了。如果我要确定n的質因子數量，隻需要計算出m值即可。首先求出這個數二進制的最高位的值p，即代碼Integer.highestOneBit(n)，然後通過

計算出m，但是Java沒有2為底的對數，隻能用對數公式計算了。

素數分解質因數法

        根據分解質因數的定義，可以知道，我們得到的結果全是素數，假設我們将√n前面所有素數全取出來，具體細節參考如何求取指定範圍的素數集，然後一個一個求餘，這樣也能将所有質因子求出來。代碼如下：

public static int[] factor(int n){
    if(n < 0){
        throw new IllegalArgumentException("N must be a non negative integer.");
    }
    if(n < 4){
        return new int[]{n};
    }
    int factorNums = (int)(Math.log(Integer.highestOneBit(n)) / Math.log(2));
    int[] factors = new int[factorNums];
    int factorCount = 0;
    int[] primes = primes((int) Math.sqrt(n));
    int primeNums = primes.length;
    for(int i = 0; i < primeNums; ){
        int prime = primes[i];
        if(n % prime == 0){
            factors[factorCount++] = prime;
            n /= prime;
        }else{
            i++;
        }
    }
    if(n != 1){ // N is a prime number.
        factors[factorCount++] = n;
    } 
    factors = Arrays.copyOf(factors, factorCount);
    Arrays.sort(factors); // These prime numbers in array are in disorder.
    return factors;
}
           

Matlab2014a版分解質因數法

        接下來介紹的是Matlab2014a版的factor方法，主要是給大家多提供點思路。

public static int[] factor(int n){
    if(n < 0){
        throw new IllegalArgumentException("N must be a non negative integer.");
    }
    if(n < 4){
        return new int[]{n};
    }
    int factorNums = (int)(Math.log(Integer.highestOneBit(n)) / Math.log(2));
    int[] factors = new int[factorNums];
    int factorCount = 0;
    int[] primes = primes((int) Math.sqrt(n));
    while(true){
        int primeProd = 1;
        for(int prime : primes){
            if(n % prime == 0){
               factors[factorCount++] = prime;
               primeProd *= prime;
            }
        }
        if(primeProd == 1){ // Now, n is a prime number.
            factors[factorCount++] = n;
            break;
        }
        if((n = n / primeProd) <= 1){
            break;
        }
    }    
    factors = Arrays.copyOf(factors, factorCount);
    Arrays.sort(factors); // These prime numbers in array are in disorder.
    return factors;
}
           

        其實，第二種方法和這種方法原理相同，但看起來，第二種方法比這種方法效率要高。在Java平台上，可能的确如此，但是在Matlab平台下，這就不一定了，畢竟兩者優化的側重點不同。

後記

        這兩天終于把素數相關的東西學了點，雖然學的非常淺，連皮毛都不到，但代碼寫起來還是很舒服。一想到此時刻正是11月10日23：58分，别人的購物快樂，我卻什麼都沒有，哎！！！