BigInteger 类在 Java 中提供了对任意精度的整数进行操作的功能
- 导入所需的库：
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
- 编写一个用于计算最大公约数（GCD）的方法，该方法使用欧几里得算法：
public static BigInteger gcd(BigInteger a, BigInteger b) {
return b.equals(BigInteger.ZERO) ? a : gcd(b, a.mod(b));
}
- 编写一个用于分解大整数的方法，该方法基于以下原理：若
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;
}
- 使用这些方法对大整数进行因式分解：
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，并输出其因子。请注意，这个方法可能不是最高效的因式分解算法，但它适用于大整数的因式分解。在实际应用中，您可能需要根据具体需求选择更高效的算法。
