algorithm - 快速确定数字是否整除集合中的任何元素

Question

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

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

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

Answer 1

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