求助：用Dart生成大数21001713200000的升序除数（解决溢出与效率）

问题分析 #

你要处理的数字21,001,713,200,000虽为14位，但并未超出64位整数的最大值（9,223,372,036,854,775,807），但暴力遍历找除数不仅效率极低（完全无法在10秒内完成），还可能在计算过程中触发溢出。另外你提供的测试代码逻辑存在错误，连小数字40的除数都无法正确生成，更无法处理大数。

正确解决方案：质因数分解+除数生成 #

高效生成所有除数的核心思路是先对目标数做质因数分解，再通过质因数的组合生成所有除数，这种方法的时间复杂度远低于暴力遍历，完全能在10秒内完成。

步骤1：质因数分解

将目标数分解为若干质数的幂次乘积形式，例如 N = p1^a1 * p2^a2 * ... * pn^an。

步骤2：生成所有除数

基于质因数分解结果，每个除数都是各质因数从0到对应幂次的组合乘积，最后排序即可（也可在生成过程中保证顺序）。

Dart代码实现 #

// 质因数分解函数，返回质数与对应指数的映射
Map<BigInt, int> factorize(BigInt n) {
  Map<BigInt, int> factors = {};
  
  // 先处理2的倍数
  while (n.isEven) {
    factors[BigInt.two] = (factors[BigInt.two] ?? 0) + 1;
    n = n ~/ BigInt.two;
  }
  
  // 处理奇数因数，遍历到sqrt(n)即可
  BigInt i = BigInt.from(3);
  while (i * i <= n) {
    while (n % i == BigInt.zero) {
      factors[i] = (factors[i] ?? 0) + 1;
      n = n ~/ i;
    }
    i += BigInt.two;
  }
  
  // 若剩余的n是质数
  if (n > BigInt.one) {
    factors[n] = 1;
  }
  
  return factors;
}

// 根据质因数生成所有除数
List<BigInt> generateDivisors(Map<BigInt, int> factors) {
  List<BigInt> divisors = [BigInt.one];
  
  for (var entry in factors.entries) {
    BigInt prime = entry.key;
    int exponent = entry.value;
    List<BigInt> temp = [];
    
    // 对已有除数，乘以当前质数的1到exponent次幂，生成新除数
    for (var d in divisors) {
      BigInt current = d;
      for (int i = 1; i <= exponent; i++) {
        current *= prime;
        temp.add(current);
      }
    }
    
    divisors.addAll(temp);
  }
  
  // 升序排序
  divisors.sort();
  return divisors;
}

void main() {
  // 用BigInt处理大数，彻底避免溢出
  BigInt target = BigInt.parse('21001713200000');
  
  // 分解质因数
  var factors = factorize(target);
  print('质因数分解结果：$factors');
  
  // 生成所有除数
  var divisors = generateDivisors(factors);
  print('总除数数量：${divisors.length}');
  print('前10个除数：${divisors.take(10)}');
  print('最后10个除数：${divisors.skip(divisors.length - 10)}');
}

代码说明 #

1. BigInt处理：不管数字多大，都能完全避免溢出问题，适配所有大数场景。
2. 高效质因数分解：仅需遍历到目标数的平方根，对于21,001,713,200,000来说，平方根约458万，遍历速度极快。
3. 组合生成除数：通过迭代组合质因数的幂次，生成所有可能的除数，最后排序即可得到升序结果。

内容的提问来源于stack exchange，提问作者João Octávio