arrays - 查找数组的最大元素是另一个元素的约数

Question

给定一个长度为 N 的非零整数数组。编写一个函数，返回数组的最大元素，该元素是同一数组中其他元素的约数。如果此数字不存在，则返回 0。我知道如何在 O(n^2) 中解决。有没有可能做得更快？

Answer 1

首先，请注意，您假设可以在 O(1) 内完成测试整数 A 是否能整除整数 B。我猜您还假设不允许预先计算(例如构建 divisibility graph )。

自 integer factorization (没有已知的多项式算法)不是一个选项，你不能比 O(n^2) 更快(最坏的情况)。

例如，给定输入 {11,127, 16139}(所有整数都是质数，每个整数的平方都小于下一个整数)，您无法避免检查所有对。