如何使用 BigInteger 对大数进行因式分解

BigInteger 类在 Java 中提供了对任意精度的整数进行操作的功能

1. 导入所需的库：

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

2. 编写一个用于计算最大公约数（GCD）的方法，该方法使用欧几里得算法：

public static BigInteger gcd(BigInteger a, BigInteger b) {
    return b.equals(BigInteger.ZERO) ? a : gcd(b, a.mod(b));
}

3. 编写一个用于分解大整数的方法，该方法基于以下原理：若 n = a * b，则 gcd(n, a) = gcd(a, n % a)。通过不断更新 a 和 n 的值，直到找到最大公约数，然后使用该公约数来分解 n：

public static List<BigInteger> factorize(BigInteger n) {
    List<BigInteger> factors = new ArrayList<>();
    BigInteger divisor = BigInteger.ONE;

    while (!divisor.equals(n)) {
        BigInteger temp = divisor;
        while (n.mod(temp).equals(BigInteger.ZERO)) {
            factors.add(temp);
            n = n.divide(temp);
        }
        divisor = divisor.nextProbablePrime();
    }

    factors.add(n); // 将最后的 n 添加到因子列表中
    return factors;
}

4. 使用这些方法对大整数进行因式分解：

public static void main(String[] args) {
    BigInteger number = new BigInteger("12345678901234567890");
    List<BigInteger> factors = factorize(number);

    System.out.println("Factorized number: " + number);
    System.out.println("Factors: " + factors);
}

这个示例将分解数字 12345678901234567890，并输出其因子。请注意，这个方法可能不是最高效的因式分解算法，但它适用于大整数的因式分解。在实际应用中，您可能需要根据具体需求选择更高效的算法。