快速确定数字是否分割集合中的任何元素

是否有算法可以快速确定数字是否是给定数字集合的因子？快速确定数字是否分割集合中的任何元素

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

难道还有比线性搜索O(n)一个更好的办法？该集合将包含几百万个元素。我不需要找到这个号码，只是一个true或false的结果。

2012-05-08 user1350004

听起来就像你正在寻找** integer factorisation **。 AFAIK，这不是在量子计算之外存在多项式时间解的问题。 –

是否订购了集合？该集的元素范围是否受到任何限制？最佳算法总是依赖于良好的数据知识，如果你知道更多，告诉我们更多。 –

该集可以排序。元素的范围在0 - 10^12之间。 – user1350004

我想一般O（n）的搜索是你到底是什么了。但是，根据数字的大小，通过观察如果您正在寻找可以被D整除的数字，并且您具有可以被D整除的数字，则可以在相当程度上加快搜索速度（假设您可以这样做）当前扫描的x和x是不是由d整除，下一个可能的候选显然在地板（[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-08 10:58:57

如果对一个恒定的列表进行检查大量数字的一个可能的方法来加快这一进程是在列表中的第一个数字因式分解到他们的首要因素。然后将列表成员放在字典中，并将主要因素作为关键字。然后，当一个数字（潜在因素）出现时，您首先将其分解为其主要因素，然后使用构造的字典来检查数字是否是可能是给定数字的可能倍数的数字的因子。

来源

2012-05-08 11:13:07 fireant

测试许多潜在因素对恒定的设定，你应该意识到，如果设定的一个元素只是两个人的多，这是不相关的，可以删除。这种方法是一种被称为Sieve of Eratosthenes的古老算法的变体。交易测试考生的数量庞大，当启动时间为运行时间：

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

您现在剩下一个小得多的组，以进行彻底测试。为了提高效率，您需要一个允许O（1）删除的数据结构，就像链接列表一样，或者只需用零替换“已删除”的元素，然后将非零元素复制到新的容器中。

来源

2012-05-08 11:36:16 smocking

我不知道这个问题的，所以让我问另一个：是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过，如果你达到数的列表的末尾报告假纳秒无0

余我们举两个例子。首先，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]的因子。

该算法的一个变体最近用于attack RSA密码系统;你可以阅读关于攻击是如何工作的here。

来源

2012-05-08 13:49:22 user448810

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

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

如果你不能在内存中获取整个集合，然后将其分解成适合内存的块和将这些块存储在磁盘上可能是一种方式。您可以将集合的根分支和上分支存储在内存中，并使用它们索引到磁盘上。保存在内存中的那部分树的深度是你应该自己决定的，但是如果你需要比根和分支的两级更多的东西，在磁盘上给出8块，我会感到惊讶。

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

我会以相反的方式处理这部分问题：生成给定数字的倍数并搜索它们中的每一个。如果您的套件有10^7元素，则任何给定编号N的套件中将有大约(10^7)/N倍数。如果从[0..10^12]范围内随机抽取给定数字，则N的平均值为0.5*10^12，这表明（与直觉相反），在大多数情况下，您只需搜索N本身。

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

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

来源

2012-05-08 14:15:10

一个快速解决方案，它需要一些预先计算：

整理一套二叉树的规则如下：一组

数字是在叶子上。
树的根包含r所有素数的最小值，它们除以一组数。
左子树对应于r的倍数的子集（除以r以便r将不会无限重复）。
右子树对应于不是r的倍数的子集。

如果你想测试一个数除以N设定的一些要素，计算它的素数分解并办理树，直到到达叶。如果叶片包含数字，则N将其分开，否则，如果叶片为空，则N不会将该组中的元素分开。

来源

2012-05-08 23:09:45 Thomash

只需计算该组的乘积并用测试因子对结果进行修改即可。在您的例子 {24,33,52} P = 41184

TF 12：41184模12 = 0真 TF 5：41184 MOD 5 = 4假

该组可以被分成块，如果计算产品会溢出计算器的算术运算，但通过存储字符串可能会产生大量数字。

来源

2017-07-10 11:45:52

快速确定数字是否分割集合中的任何元素

回答

相关问题