0

有没有一种算法可以快速确定一个数字是否是给定数字集的一个因子？

例如，12是一个因素，[24,33,52]而5不是。

有比线性搜索更好的方法O(n)吗？该集合将包含几百万个元素。我不需要找到数字，只需一个true或false结果。

4

7 回答 7

1

如果根据常量列表检查大量数字，一种可能的加速过程的方法是首先将列表中的数字分解为它们的素因子。然后将列表成员放入字典中，并将主要因素作为键。然后，当一个数字（潜在因子）出现时，您首先将其分解为其主要因子，然后使用构造的字典检查该数字是否是可能是给定数字的潜在倍数的数字的因子。

于 2012-05-08T11:13:07.210 回答
0

由于要搜索的集合是固定的，因此花费在组织搜索集合上的任何时间都是值得的。如果您可以在内存中获取该集合，那么我希望二叉树结构会适合。平均而言，在二叉树中搜索元素是一项O(log n)操作。

如果您有理由相信集合中的数字在整个范围内均匀分布，[0..10^12]那么对内存中排序集合的二进制搜索应该与搜索二叉树一样执行。另一方面，如果集合（或集合的任何子集）中的中间元素预计不会接近集合（或子集）所包含范围内的中间值，那么我认为二叉树会更好（实际）表现。

如果您无法将整个集合放在内存中，那么将其分解为适合内存的块并将这些块存储在磁盘上可能是可行的方法。您可以将集合的根分支和上分支存储在内存中，并使用它们在磁盘上建立索引。保存在内存中的树部分的深度是您应该自己决定的，但如果您需要的不仅仅是根和 2 级分支，在磁盘上提供 8 个块，我会感到惊讶。

当然，这只能解决您的部分问题，查找给定的数字是否在集合中；你真的想知道给定的数字是否是集合中任何数字的因数。正如我在评论中所建议的那样，我认为任何基于对集合中的数字进行因式分解的方法都是没有希望的，它给出了超出多项式时间的预期运行时间。

我会反过来处理这部分问题：生成给定数字的倍数并搜索它们中的每一个。如果你的集合有10^7元素，那么任何给定的数字在集合中N都会有大约(10^7)/N倍数。如果给定的数字是从范围中随机抽取的，[0..10^12]则平均值N是0.5*10^12，这表明（与直觉相反）在大多数情况下您只需搜索N自身。

是的，我知道在许多情况下您将不得不搜索更多的值。

这种方法相对容易并行化。

于 2012-05-08T14:15:10.250 回答
0

需要一些预计算的快速解决方案：

使用以下规则将您的集合组织在二叉树中：

  • 集合的数字在叶子上。
  • 树的根包含r所有素数中的最小值，这些素数除以集合中的一个数。
  • 左子树对应于r（除以r，r不会无限重复）的倍数的子集。
  • 右子树对应于数字的子集，而不是 的倍数r。

如果你想测试一个数是否能N整除集合中的某个元素，计算它的素数分解并遍历树直到你到达叶子。如果叶子包含一个数字，则N除以它，否则如果叶子为空，则不N除集合中的任何元素。

于 2012-05-08T23:09:45.773 回答
0

我认为通常 O(n) 搜索是你最终会得到的。但是，根据一般数字的大小，您可以通过观察如果您正在搜索找到一个可被 D 整除的数字并且您有当前扫描的 x 和 x 不能被 D 整除，下一个可能的候选者显然在 floor([x + D] / D) * D。也就是说，如果 D = 12 并且列表为

5 11 13 19 22 25 27

并且您正在扫描 13，下一个可能的候选编号将是 24。现在根据您输入的分布，您可以使用二分搜索而不是线性搜索向前扫描，因为您现在正在搜索不少于 24 的最小数字在列表中，并且列表已排序。如果 D 很大，那么您可以通过这种方式节省大量比较。

然而，从纯粹的计算复杂度的角度来看，排序然后搜索将是 O(n log n)，而线性扫描是 O(n)。

于 2012-05-08T10:58:57.137 回答
0

我不确定这个问题，所以让我再问一个问题：12 是 [6,33,52] 的因数吗？很明显，12 不能整除 6、33 或 52。但 12 的因数是 2*2*3，而 6、33 和 52 的因数是 2*2*2*3*3*11*13。12 的所有因子都存在于集合 [6,33,52] 中，具有足够的多重性，因此您可以说 12 是 [6,33,52] 的因子。

如果你说 12 不是 [6,33,52] 的因数，那么没有比测试每个数是否能被 12 整除更好的解决方案了；只需执行除法并检查余数。因此 6%12=6、33%12=9 和 52%12=4，所以 12 不是 [6.33.52] 的因数。但是如果你说 12是[6,33,52] 的因数，那么要确定数字f是否是集合ns的因数，只需将数字ns依次相乘，每次相乘后取余模f，如果余数曾经为 0，则立即报告true ，如果您到达数字列表的末尾而没有余数 0，则报告false。

让我们举两个例子。首先，12 是 [6,33,52] 的因数吗？第一次（微不足道的）乘法结果为 6，余数为 6。现在 6*33=198，除以 12 余数为 6，我们继续。现在 6*52=312 和 312/12=26r0，所以余数为 0，结果为true。其次，5 是 [24,33,52] 的因数吗？乘法链为24%5=5，(5*33)%5=2，(2*52)%5=4，所以5不是[24,33,52]的因数。

该算法的一个变体最近被用于攻击RSA 密码系统；您可以在此处了解攻击的工作原理。

于 2012-05-08T13:49:22.630 回答
0

为了针对一个常数集合测试许多潜在因素，您应该意识到，如果集合中的一个元素只是其他两个元素的倍数，则它是无关紧要的，可以删除。这种方法是一种称为埃拉托色尼筛法的古老算法的变体。测试大量候选人时，用启动时间换取运行时间：

  1. 选择集合中>1的最小数字
  2. 从集合中删除该数字的任何倍数，除了它本身
  3. 对下一个最小的数字重复 2，进行一定次数的迭代。迭代次数将取决于与启动时间的权衡

你现在只剩下一个小得多的集合来进行详尽的测试。为了提高效率，您要么需要一个允许 O(1) 删除的集合的数据结构，如链表，要么只需将“已删除”元素替换为零，然后将非零元素复制到新容器中。

于 2012-05-08T11:36:16.260 回答
0

只需计算集合的乘积并使用测试因子对结果进行修正。在您的示例中 {24,33,52} P=41184

Tf 12：41184 mod 12 = 0 真 Tf 5：41184 mod 5 = 4 假

如果计算乘积会溢出计算器的算术，则可以将集合分成块，但是通过存储字符串可能会产生巨大的数字。

于 2017-07-10T11:45:52.470 回答