Dart中如何判断整数i可一次性整除列表所有元素以求解最大公约数

现有代码修复 #

你当前的错误点是不能直接对列表_num做取模运算，需要遍历列表所有元素判断是否都能被i整除，Dart 列表内置的every方法可以直接实现这个逻辑，修复后代码如下：

_num.sort();
List<int> _answer = [];

for (int i = 1; i <= _num.last; i++) {
  // 判断所有元素都可被i整除且余数为0
  if (_num.every((element) => element % i == 0)) {
    _answer.add(i);
  }
}
// 遍历结束后_answer最后一个元素就是最大公约数
int finalGcd = _answer.last;

这个暴力遍历的方案适合小数值场景，数值过大会存在性能问题。

更优实现：辗转相除法（欧几里得算法） #

该算法时间复杂度远低于暴力遍历，实现逻辑是先写两个数的最大公约数计算函数，再对列表做两两迭代计算即可，代码示例如下：

// 计算两个非负整数的最大公约数
int calculateGcd(int a, int b) {
  // 处理负数场景可先对a、b取绝对值
  while (b != 0) {
    final temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

// 计算整个整数列表的最大公约数
int calculateListGcd(List<int> numList) {
  // 可自行添加空列表、单元素列表的边界校验
  return numList.reduce(calculateGcd);
}

// 调用测试
void main() {
  List<int> _num = [16, 24, 32];
  print(calculateListGcd(_num)); // 输出结果为8
}

内容的提问来源于stack exchange，提问作者Somxhai