Java算法之?dāng)?shù)論基礎(chǔ)

Java算法之?dāng)?shù)論基礎(chǔ)

一、最大公約數(shù)（Greatest Common Divisor, GCD）

在Java中，我們可以使用歐幾里得算法（輾轉(zhuǎn)相除法）來求兩個(gè)數(shù)的最大公約數(shù)：

輾轉(zhuǎn)相除法（歐幾里得算法）

輾轉(zhuǎn)相除法，也稱為歐幾里得算法（Euclidean Algorithm），是一種用于計(jì)算兩個(gè)非負(fù)整數(shù)最大公約數(shù)（Greatest Common Divisor, GCD）的經(jīng)典算法。該算法基于這樣一個(gè)事實(shí)：對(duì)于任何兩個(gè)非零自然數(shù)a和b，它們的最大公約數(shù)等于a除以b的余數(shù)c和b之間的最大公約數(shù)。

算法步驟如下：

  1. 初始化兩個(gè)整數(shù)a和b，其中a >= b且b > 0。
  2. 計(jì)算a除以b的余數(shù)，記作r（即r = a % b）。
  3. 如果r為0，則b就是a和b的最大公約數(shù)。
  4. 否則，令a等于原來的b，b等于剛才得到的余數(shù)r，然后回到第二步繼續(xù)迭代。

下面是Java實(shí)現(xiàn)輾轉(zhuǎn)相除法求最大公約數(shù)的代碼：

public static int gcd(int a, int b) {
    // 確保a >= b
    if (a < b) {
        int temp = a;
        a = b;
        b = temp;
    }

    // 輾轉(zhuǎn)相除直到余數(shù)為0
    while (b != 0) {
        int remainder = a % b;
        a = b;
        b = remainder;
    }

    // 這時(shí)a就是a和b的最大公約數(shù)
    return a;
}

這個(gè)算法的關(guān)鍵在于通過不斷替換較大的數(shù)為較小數(shù)和余數(shù)，使得每次迭代中，兩個(gè)數(shù)的差值逐漸縮小，并最終找到它們的最大公約數(shù)。由于每次迭代都會(huì)使其中一個(gè)數(shù)至少減小一半，因此該算法具有較高的效率。

除了輾轉(zhuǎn)相除法，還有其他幾種算法，但是與輾轉(zhuǎn)相除法相比，效率會(huì)稍微差一些，下面列舉幾種其他算法：

  1. 更相減損法：
    更相減損法是中國(guó)古代數(shù)學(xué)家劉徽提出的求解最大公約數(shù)的方法，其原理是連續(xù)用較大數(shù)減去較小數(shù)，直至兩數(shù)相等，此時(shí)的數(shù)即為兩數(shù)的最大公約數(shù)。但這種方法在數(shù)值相差懸殊的情況下迭代次數(shù)可能會(huì)較多，不如輾轉(zhuǎn)相除法高效。

    例如，對(duì)于數(shù)a和b，先比較a和b的大小，若a>b，則用a-b并將結(jié)果代替a；若a<b，則用b-a并將結(jié)果代替b。重復(fù)上述過程，直到a=b為止。

  2. 素因數(shù)分解法：
    將兩個(gè)數(shù)分別進(jìn)行素因數(shù)分解，找出它們共有的素因數(shù)，并把相同的素因數(shù)各取最小指數(shù)次冪相乘，所得積即為兩數(shù)的最大公約數(shù)。這種方法直觀易理解，但對(duì)于大數(shù)可能不如輾轉(zhuǎn)相除法快速有效。

    相同的素因數(shù)各取最小指數(shù)次冪相乘，這似乎有些拗口，對(duì)它簡(jiǎn)單解釋一下，舉個(gè)例子

a = 12 = 22 × 31 ······ b = 18 = 21 × 32

a和b這兩個(gè)數(shù)，有2和3這兩個(gè)相同的素因數(shù)，在a中，2的指數(shù)是2，在b中，2的指數(shù)是1，那么素因數(shù)2的最小指數(shù)次冪就是1，3同理也是1。

但是對(duì)于找最大公約數(shù)這個(gè)問題，素?cái)?shù)分解法明顯麻煩許多，因?yàn)楣馐钦夜餐乃匾驍?shù)，就已經(jīng)比較麻煩了，所以個(gè)人并不推薦用這種方法來求最大公約數(shù)。只是提供一個(gè)思想。

以上方法各有特點(diǎn)，對(duì)于不同的應(yīng)用場(chǎng)景和需求可以選擇最合適的算法。在大多數(shù)情況下，特別是中小規(guī)模的整數(shù)求最大公約數(shù)，輾轉(zhuǎn)相除法是最常用且效率最高的。

二、最小公倍數(shù)（Least Common Multiple, LCM）

最小公倍數(shù)，當(dāng)看到這個(gè)題目時(shí)，我們可能最先想到拿較小的那個(gè)數(shù)加倍，然后判斷另一個(gè)數(shù)能否被整除，這里提供另一個(gè)方法

求兩個(gè)正整數(shù) (a) 和 (b) 的最小公倍數(shù)的一種常見方法是利用它們的最大公約數(shù)，記作 (gcd(a, b))。根據(jù)數(shù)學(xué)性質(zhì)，(a) 和 (b) 的最小公倍數(shù)可以通過它們的乘積除以它們的最大公約數(shù)來得到：

LCM(a, b) = \frac{|a \times b|}{gcd(a, b)}
這里的絕對(duì)值符號(hào)僅是為了確保在 (a) 或 (b) 中有負(fù)數(shù)時(shí)仍能得出正確的結(jié)果，但由于最小公倍數(shù)定義應(yīng)用于正整數(shù)，所以一般情況下 (a) 和 (b) 都是正數(shù)，因此實(shí)際上不需要取絕對(duì)值。

如果你已經(jīng)知道 (a) 和 (b) 的最大公約數(shù)，可以直接套用上述公式。若不知道最大公約數(shù)，可以先用例如歐幾里得算法或者其他更高級(jí)的算法來求出 (gcd(a, b))。

舉個(gè)例子，假設(shè)要找出 (a = 12) 和 (b = 18) 的最小公倍數(shù)：

首先計(jì)算它們的最大公約數(shù) (gcd(12, 18))。我們可以直接使用歐幾里得算法，計(jì)算出他們的最大公約數(shù)為6。

接下來，代入上面的公式計(jì)算最小公倍數(shù)：

LCM(12, 18) = \frac{12 \times 18}{6} = 36
所以，(12) 和 (18) 的最小公倍數(shù)是 (36)。

三、快速冪算法

Java快速冪算法是一種高效的算法，用于計(jì)算任意數(shù) a 的非負(fù)整數(shù)指數(shù) n 的次方，即計(jì)算 (a^n) 的值。傳統(tǒng)方法是通過連續(xù)乘法，時(shí)間復(fù)雜度為 (O(n))，但快速冪算法利用了指數(shù)運(yùn)算法則以及二進(jìn)制表示，將時(shí)間復(fù)雜度降低到了 (O(\log_2 n))。

快速冪的基本思想：

  1. 將指數(shù) n 轉(zhuǎn)換成二進(jìn)制形式，例如 n = b_{m-1}...b_1b_0，其中 (b_i) 是二進(jìn)制位。
  2. 利用指數(shù)的二進(jìn)制表示，將 (a^n) 分解成一系列的平方操作和乘法操作。
    • 對(duì)于每一位 (b_i)，如果它是1，則我們需要將當(dāng)前的結(jié)果與基數(shù) a 相乘；如果是0，則不需要。
    • 因?yàn)槊看味际瞧椒胶筮x擇性地乘以基數(shù)，所以問題轉(zhuǎn)化為 (a{2k}) 的計(jì)算，這可以通過遞歸或者循環(huán)迭代完成。

以下是一個(gè)基本的Java實(shí)現(xiàn)示例：

public long power(long base, int exponent) {
    // 邊界條件
    //當(dāng)指數(shù)為0時(shí)，返回結(jié)果1
    if (exponent == 0)
        return 1;
    //當(dāng)?shù)讛?shù)為0時(shí)，返回結(jié)果0
    if (base == 0)
        return 0;
    //定義初始化結(jié)果為1
    long result = 1;
    //定義一個(gè)數(shù)記錄每次循環(huán)后的平方數(shù)
    long currentBase = base;

    //將指數(shù)轉(zhuǎn)換為二進(jìn)制并從最高位開始處理
    while (exponent != 0) {
        // 進(jìn)行與運(yùn)算，如果當(dāng)前位是1，則進(jìn)行乘法
        if ((exponent & 1) != 0) {
            result *= currentBase;
        }
        //把基數(shù)平方，因?yàn)榇藭r(shí)是二進(jìn)制的表示，如果為1的話，那么就代表要乘這個(gè)數(shù)兩次
        currentBase *= currentBase;
        //移動(dòng)到下一個(gè)二進(jìn)制位
        exponent >>= 1;
    }

    return result;
}

對(duì)于需要同時(shí)計(jì)算 a^n 對(duì)某個(gè)模數(shù) p 取模的情況，即求 (a^n mod p)，可以在每一步乘法后立即對(duì)結(jié)果取模，避免溢出：

public long powerModulo(long base, int exponent, long mod) {
    //邊界條件
    if (base == 0)
        return 0;
    if (exponent == 0)
        return 1;
    //初始化結(jié)果
    long result = 1;
    //基數(shù)為底數(shù)模上mod
    long currentBase = base % mod;
    //將指數(shù)轉(zhuǎn)換為二進(jìn)制并從最高位開始處理
    while (exponent != 0) {
        if ((exponent & 1) != 0) {
            //對(duì)結(jié)果乘上基數(shù)，并模上mod
            result = (result * currentBase) % mod;
        }
        currentBase = (currentBase * currentBase) % mod;
        exponent >>= 1;
    }

    return result;
}

這樣，無論 n 多大，都可以高效地計(jì)算出 a 的 n 次冪及其模運(yùn)算結(jié)果。

對(duì)于取模運(yùn)算的性質(zhì)，（result * currentBase * currentBase）%mod = result %mod * currentBase % mod * currentBase % mod,所以每次計(jì)算都需要對(duì)結(jié)果取模。

四、矩陣快速冪

矩陣快速冪常用于處理矩陣乘法連乘問題，比如在某些數(shù)論和圖論問題中：

矩陣快速冪就只是把乘法換成了矩陣乘法，掌握了快速冪運(yùn)算再去學(xué)矩陣快速冪就很簡(jiǎn)單了，難一些的地方可能就是矩陣的乘法需要掌握。

public static int[][] matrixPower(int[][] matrix, int p) {
    int n = matrix.length;
    //初始化矩陣為單位矩陣
    int[][] res = new int[n][n];
    for (int i = 0; i < n; i++) {
        res[i][i] = 1;
    } 
    while (p > 0) {
        if ((p & 1) != 0) { // 如果p是奇數(shù)
            res = multiply(res, matrix);
        }
        matrix = multiply(matrix, matrix); // 把matrix自乘
        p >>= 1; // p /= 2 (right shift)
    }
    return res;
}
// 定義矩陣乘法函數(shù)multiply
public static int[][] multiply(int[][] matrixA, int[][] matrixB) {
        //n為第一個(gè)數(shù)組的行數(shù)，m為第二個(gè)數(shù)組的列數(shù)，p為第二個(gè)數(shù)組的行數(shù)
        int n = matrixA.length, p = matrixB.length, m = matrixB[0].length;
        //過第二個(gè)數(shù)組的行數(shù)不等于第一個(gè)數(shù)組的列數(shù)，不能相乘
        if (p != matrixA[0].length)
            return null;
        int[][] ans = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < p; k++)
                    ans[i][j] += (matrixA[i][k] % mod) * (matrixB[k][j] % mod) % mod;
                ans[i][j] = ans[i][j] % mod;
            }
        return ans;
    }

五、高斯消元法

高斯消元用于求解線性方程組，不過在數(shù)論中可能更多的是用于理論推導(dǎo)和簡(jiǎn)化問題：

// 假設(shè)A是一個(gè)n*n的系數(shù)矩陣，b是一個(gè)n*1的常數(shù)列組成的數(shù)組，組合起來形成增廣矩陣[A|b]
// 下面的代碼將求解線性方程組Ax=b

public class GaussElimination {
    public static double[] solveLinearEquations(double[][] augmentedMatrix) {
        int n = augmentedMatrix.length;
        for (int i = 0; i < n; i++) {
            // 1. 選擇主元（pivot）: 通常選當(dāng)前行中絕對(duì)值最大的元素對(duì)應(yīng)的列，若有零元素則嘗試交換行
            int maxPivotRowIndex = findMaxPivotRowIndex(i, augmentedMatrix, n);

            // 交換行（如果當(dāng)前行的主元不是最大的）
            swapRows(i, maxPivotRowIndex, augmentedMatrix);

            // 2. 主元?dú)w一化：將主元所在的行除以其主元值，使其變?yōu)?
            double pivot = augmentedMatrix[i][i];
            divideRowByItsPivot(i, pivot, augmentedMatrix);

            // 3. 消元：逐行消除當(dāng)前主元下方元素
            for (int j = i + 1; j < n; j++) {
                double factor = augmentedMatrix[j][i] / augmentedMatrix[i][i];
                subtractMultipleFromRow(j, i, factor, augmentedMatrix);
            }
        }

        // 解決得到的上三角矩陣（RREF），從底部向上回代求解
        double[] solutions = new double[n];
        for (int i = n - 1; i >= 0; i--) {
            solutions[i] = augmentedMatrix[i][n] / augmentedMatrix[i][i];
            for (int j = i - 1; j >= 0; j--) {
                augmentedMatrix[j][n] -= augmentedMatrix[j][i] * solutions[i];
            }
        }

        return solutions;
    }

    // 輔助方法
    private static int findMaxPivotRowIndex(int startRow, double[][] matrix, int n) {
        double maxPivot = Math.abs(matrix[startRow][startRow]);
        int maxRowIndex = startRow;
        for (int i = startRow + 1; i < n; i++) {
            if (Math.abs(matrix[i][startRow]) > maxPivot) {
                maxPivot = Math.abs(matrix[i][startRow]);
                maxRowIndex = i;
            }
        }
        return maxRowIndex;
    }

    private static void swapRows(int row1, int row2, double[][] matrix) {
        double[] tempRow = matrix[row1];
        matrix[row1] = matrix[row2];
        matrix[row2] = tempRow;
    }

    private static void divideRowByItsPivot(int rowIndex, double pivot, double[][] matrix) {
        for (int j = rowIndex; j < matrix[rowIndex].length; j++) {
            matrix[rowIndex][j] /= pivot;
        }
    }

    private static void subtractMultipleFromRow(int targetRow, int sourceRow, double factor, double[][] matrix) {
        for (int j = sourceRow; j < matrix[targetRow].length; j++) {
            matrix[targetRow][j] -= factor * matrix[sourceRow][j];
        }
    }
}

六、素?cái)?shù)篩法

埃拉托斯特尼篩法（Sieve of Eratosthenes）用于生成一定范圍內(nèi)的素?cái)?shù)序列：

原理就是把2的倍數(shù)，3的倍數(shù)等等都標(biāo)記一下，那么剩下的就是素?cái)?shù)了，代碼如下

public class PrimeSieve {
    //篩選
    public static boolean[] sieveOfEratosthenes(int limit) {
        //初始化數(shù)組，先把數(shù)據(jù)都初始化為true
        boolean[] isPrime = new boolean[limit + 1];
        for (int i = 2; i <= limit; i++) {
            isPrime[i] = true;
        }

        // 基本原理：標(biāo)記2的倍數(shù)（除了2本身），接著標(biāo)記3的倍數(shù)（除了3本身），以此類推...
        for (int p = 2; p * p <= limit; p++) {
            if (isPrime[p]) {  // p是素?cái)?shù)
                for (int i = p * p; i <= limit; i += p) {
                    isPrime[i] = false;  // 將p的倍數(shù)標(biāo)記為非素?cái)?shù)
                }
            }
        }

        return isPrime;
    }
//篩選素?cái)?shù)
    public static List<Integer> getPrimesUpTo(int limit) {
        boolean[] primes = sieveOfEratosthenes(limit);
        List<Integer> primeList = new ArrayList<>();
        for (int i = 2; i <= limit; i++) {
            if (primes[i]) {
                primeList.add(i);
            }
        }
        return primeList;
    }

    public static void main(String[] args) {
        int limit = 100;
        List<Integer> primes = getPrimesUpTo(limit);
        System.out.println("素?cái)?shù)列表（小于或等于 " + limit + "）：");
        System.out.println(primes);
    }
}

七、唯一分解定理

唯一分解定理指出每個(gè)大于1的整數(shù)都可以唯一地表示為若干個(gè)素?cái)?shù)的積的形式。在Java中可以編寫函數(shù)尋找一個(gè)數(shù)的所有素?cái)?shù)因子：

public static class PrimeFactorization {
        // 定義一個(gè)方法primeFactorize，接收一個(gè)整數(shù)參數(shù)n，用于計(jì)算并輸出n的質(zhì)因數(shù)分解
        public static void primeFactorize(int n) {
            // 使用HashMap來存儲(chǔ)質(zhì)因數(shù)及其對(duì)應(yīng)的冪次
            Map<Integer, Integer> factors = new HashMap<>();

            // 遍歷從2到n的平方根的所有整數(shù)，因?yàn)橐粋€(gè)合數(shù)的最大質(zhì)因數(shù)不會(huì)超過其平方根
            for (int i = 2; i <= Math.sqrt(n); i++) {
                // 當(dāng)n能被當(dāng)前整數(shù)i整除時(shí)，進(jìn)入循環(huán)內(nèi)部
                while (n % i == 0) {
                    // 在factors映射表中，將質(zhì)因數(shù)i作為鍵，冪次作為值。如果i已經(jīng)在映射表中，則增加其冪次（值+1）；否則插入新的鍵值對(duì)，冪次初始化為1
                    factors.put(i, factors.getOrDefault(i, 0) + 1);
                    // 更新n的值，去除已找到的質(zhì)因數(shù)i的影響
                    n /= i;
                }
            }

            // 檢查是否還有未處理的質(zhì)因數(shù)，即n本身（當(dāng)n為質(zhì)數(shù)時(shí)）
            if (n > 1) {
                // 將n作為質(zhì)因數(shù)放入映射表中，并將冪次初始化或增加為1
                factors.put(n, factors.getOrDefault(n, 0) + 1);
            }

            // 輸出質(zhì)因數(shù)分解結(jié)果
            System.out.println("質(zhì)因數(shù)分解結(jié)果:");
            // 遍歷映射表中的所有條目（鍵值對(duì)）
            for (Map.Entry<Integer, Integer> entry : factors.entrySet()) {
                // 獲取當(dāng)前質(zhì)因數(shù)和對(duì)應(yīng)的冪次
                int prime = entry.getKey();
                int power = entry.getValue();
                // 格式化輸出質(zhì)因數(shù)和冪次
                System.out.printf("%d^%d ", prime, power);
            }
        }

        // 主函數(shù)，用于測(cè)試primeFactorize方法
        public static void main(String[] args) {
            // 設(shè)置要分解的數(shù)，例如120
            int numberToFactorize = 120;
            // 調(diào)用primeFactorize方法進(jìn)行質(zhì)因數(shù)分解并輸出結(jié)果
            primeFactorize(numberToFactorize);
        }
    }

在上述提供的質(zhì)因數(shù)分解代碼中，我們并沒有顯式地檢查每個(gè) i 是否為質(zhì)數(shù)。但實(shí)際上是隱含了這個(gè)性質(zhì)：由于我們是從2開始，每次找到一個(gè)能夠整除 n 的數(shù) i 后，都會(huì)立刻更新 n 的值為 n / i，并且將 i 作為質(zhì)因數(shù)存儲(chǔ)到 factors 中。這樣做的結(jié)果保證了 i 必然是質(zhì)因數(shù)，原因如下：

  1. 我們從2開始，2是最小的質(zhì)數(shù)。
  2. 對(duì)于每個(gè)可能的 i，只有當(dāng) n 能被 i 整除（即 n % i == 0）時(shí)，才會(huì)將 i 視為一個(gè)質(zhì)因數(shù)，并將 n 更新為 n / i。這意味著 i 必須是 n 的一個(gè)因數(shù)，而且由于我們?cè)谡屹|(zhì)因數(shù)，因此 i 必須是一個(gè)質(zhì)數(shù)（因?yàn)樗荒苡筛〉馁|(zhì)數(shù)相乘得到）。
  3. 如果 i 不是質(zhì)數(shù)，那么它可以表示為其他質(zhì)數(shù)的乘積，而這些更小的質(zhì)數(shù)肯定會(huì)在之前已經(jīng)被找出并從 n 中消去，所以當(dāng)輪到 i 時(shí)，n 不會(huì)被 i 整除。

總之，雖然代碼中沒有明確寫出判斷 i 是否為質(zhì)數(shù)的語(yǔ)句，但在整個(gè)分解過程中，實(shí)際找到的每個(gè) i 都滿足質(zhì)因數(shù)的條件，這是因?yàn)榉纸獾倪^程基于了質(zhì)數(shù)的定義和性質(zhì)。同時(shí)，由于我們僅檢查到 Math.sqrt(n) 范圍內(nèi)的數(shù)，這也保證了不會(huì)遺漏大于 Math.sqrt(n) 的質(zhì)因數(shù)，因?yàn)槿魏未笥?Math.sqrt(n) 并且小于等于 n 的合數(shù)都必定包含至少一個(gè)不大于 Math.sqrt(n) 的質(zhì)因數(shù)。

factors.getOrDefault(i, 0) + 1 這句代碼在Java集合框架中，特別是對(duì)于 Map 接口的實(shí)現(xiàn)類（如 HashMap）中使用，用來獲取與指定鍵 i 關(guān)聯(lián)的值，如果該鍵不存在于 Map 中，則返回默認(rèn)值 0。

具體來說：

  • factors.getOrDefault(i, 0)：這會(huì)嘗試從 factors 映射表中獲取鍵為 i 的值。如果 i 已經(jīng)存在于映射表中，就返回對(duì)應(yīng)的值；如果 i 不存在于映射表中，則返回默認(rèn)值 0。
  • + 1：接著對(duì)獲取的結(jié)果（無論它是從映射表中得到的實(shí)際值還是默認(rèn)值 0）加1，表示增加質(zhì)因數(shù) i 的冪次。

在質(zhì)因數(shù)分解的過程中，這句代碼的目的是統(tǒng)計(jì)每個(gè)質(zhì)因數(shù) i 出現(xiàn)的次數(shù)。每當(dāng)我們發(fā)現(xiàn) n 可以被 i 整除時(shí)，就認(rèn)為找到了一次 i 這個(gè)質(zhì)因數(shù)，于是就增加它在映射表中的計(jì)數(shù)（冪次）。如果 i 剛剛被發(fā)現(xiàn)，那么它在映射表中的值就是默認(rèn)值 0，加1之后就變?yōu)?1，表示出現(xiàn)了1次；如果 i 已經(jīng)出現(xiàn)過，那么增加的就是之前記錄的次數(shù)基礎(chǔ)上再加1。

八、約數(shù)定理

約數(shù)定理描述了正整數(shù)的約數(shù)個(gè)數(shù)與它的素因數(shù)分解之間的關(guān)系。在Java中可以實(shí)現(xiàn)函數(shù)計(jì)算一個(gè)數(shù)的約數(shù)個(gè)數(shù)：

Java中并不直接提供有關(guān)約數(shù)定理的內(nèi)置功能或API，但你可以根據(jù)約數(shù)定理的數(shù)學(xué)原理編寫程序來計(jì)算一個(gè)數(shù)的所有約數(shù)數(shù)量或列出所有約數(shù)。

約數(shù)定理（也稱為約數(shù)個(gè)數(shù)定理）表明，對(duì)于一個(gè)正整數(shù) ( n ) 可以寫成質(zhì)因數(shù)分解的形式：

n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}
其中 ( p_1, p_2, ..., p_k ) 是不同的質(zhì)數(shù)，而 ( a_1, a_2, ..., a_k ) 是正整數(shù)。根據(jù)約數(shù)定理，( n ) 的正約數(shù)總數(shù)為：

d(n) = (a_1 + 1) \times (a_2 + 1) \times \cdots \times (a_k + 1)
下面是一個(gè)簡(jiǎn)單的Java示例，展示了如何利用約數(shù)定理計(jì)算一個(gè)數(shù)的約數(shù)個(gè)數(shù)：

import java.util.HashMap;
import java.util.Map;

public class DivisorCount {
    public static int countDivisors(int n) {
        Map<Integer, Integer> primePowers = new HashMap<>();
        
        // 分解質(zhì)因數(shù)并記錄每個(gè)質(zhì)因數(shù)的冪次
        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                primePowers.put(i, primePowers.getOrDefault(i, 0) + 1);
                n /= i;
            }
        }
        
        // 如果n大于1，意味著還有一個(gè)未記錄的質(zhì)因數(shù)（n自身）
        if (n > 1) {
            primePowers.put(n, primePowers.getOrDefault(n, 0) + 1);
        }

        // 計(jì)算約數(shù)個(gè)數(shù)
        int divisorCount = 1;
        for (int power : primePowers.values()) {
            divisorCount *= (power + 1);
        }
        
        return divisorCount;
    }

    public static void main(String[] args) {
        int number = 120;
        System.out.println("Number of divisors of " + number + ": " + countDivisors(number));
    }
}

這段代碼首先找到給定整數(shù)的所有質(zhì)因數(shù)及每個(gè)質(zhì)因數(shù)的冪次，然后利用約數(shù)定理公式計(jì)算約數(shù)的數(shù)量。請(qǐng)注意，這段代碼并沒有直接使用“約數(shù)定理”的名稱，但它體現(xiàn)了約數(shù)定理的內(nèi)容和應(yīng)用。

九、反素?cái)?shù)

反素?cái)?shù)是指其真因數(shù)個(gè)數(shù)（不包括1和自身）為素?cái)?shù)的正整數(shù)。在Java中，可以先確定一個(gè)數(shù)的所有真因數(shù)，再檢查其數(shù)量是否為素?cái)?shù)：

public static boolean isPermutablePrime(int n) {
    int divisorsCount = countDivisors(n) - 2; // 減去1和自身
    return isPrime(divisorsCount);
}

// isPrime 是前面定義過的判斷素?cái)?shù)的輔助函數(shù)

總結(jié)，數(shù)論算法在Java編程中有著廣泛的應(yīng)用，理解和熟練掌握這些基礎(chǔ)算法對(duì)于解決各類問題至關(guān)重要。上述代碼僅為簡(jiǎn)要示例，實(shí)際編程時(shí)請(qǐng)根據(jù)具體需求和數(shù)據(jù)規(guī)模加以優(yōu)化和完善。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容