5

这是我思考了很久的问题。

找到从 a 到 b 的所有数字不能被从 x 到 y 的任何数字整除的最快方法是什么？

考虑一下：

我想找到从 1 到 10 的所有不能被 2 到 5 整除的数字。如果我在哪里使用线性方法，这个过程将变得非常缓慢；像这样：

result = []
a = 1
b = 10
x = 2
y = 5
for i in range(a,b):
    t = False
    for j in range(x,y):
        if i%j==0:
            t = True
            break
    if t is False:
        result.append(i)
return result

有谁知道比线性解决方案计算时间更少的任何其他方法？

如果没有，任何人都可以看到如何更快地完成此操作，因为此时我是空白的......

真诚的，约翰

[编辑]

数字的范围是 0 到 >1,e+100

这适用于 a、b、x 和 y

4

2 回答 2

4

您只需要检查可能的除数范围内的质数 - 例如，如果一个值不能被 2 整除，那么它也不能被 2 的任何倍数整除；对于其他每个素数和素数倍数也是如此。因此，在您的示例中，您可以检查2, 3, 5- 您不需要检查4，因为任何能被 4 整除的东西都必须能被 2 整除。因此，更快的方法是计算您感兴趣的任何范围内的素数，然后简单地计算哪个他们划分的价值观。

另一个加速是将您感兴趣的范围内的每个值添加到 a set：当您发现它可以被您范围内的数字整除时，将其从集合中删除。然后，您应该只测试保留在集合中的数字 - 这将阻止您多次测试数字。

如果我们结合这两种方法，我们可以看到我们可以创建set所有值的 a（因此在示例中，一个所有值都为 1 到 10 的集合），并简单地从该集合中删除第二个范围内每个素数的倍数。

编辑：正如 Patashu 指出的那样，如果除以给定值的素数不在集合中，这将不太有效。为了解决这个问题，我们可以对上述应用类似的算法：创建一个set带有值[a, b]的，对于 中的每个值set，删除它的所有倍数。因此，对于下面在评论中给出的示例（带有[3, 6]），我们将从 3 开始并删除它在集合中的倍数 - 所以6。因此，我们需要测试的剩余值将[3, 4, 5]是我们在这种情况下想要的。

Edit2：这是一个非常糟糕的、糟糕的实现，它没有被优化并且有可怕的变量名：

def find_non_factors():
    a = 1
    b = 1000000
    x = 200
    y = 1000

    z = [True for p in range(x, y+1)]
    for k, i in enumerate(z):
        if i:
            k += x
            n = 2
            while n * k < y + 1:
                z[(n*k) - x] = False
                n += 1

    k = {p for p in range(a, b+1)}

    for p, v in enumerate(z):
        if v:
            t = p + x
            n = 1
            while n * t < (b + 1):
                if (n * t) in k:
                    k.remove(n * t)
                n += 1

    return k

使用这些数字尝试您的原始实现。在我的电脑上花费 > 1 分钟。此实现需要不到 2 秒的时间。

于 2013-04-12T05:21:22.060 回答
3

终极优化警告：不要过早优化。每当您尝试优化代码时，对其进行分析以确保它需要优化，并在您打算对其进行优化的同一类型的数据上分析优化以确认它是加速。几乎所有的代码都不需要优化，只是为了给出正确的答案。

如果您正在优化小 xy 和大 ab：

创建一个长度为所有 x、x+1、x+2...y 中最小公倍数的数组。例如，对于 2、3、4、5，它将是 60，而不是 120。

现在用布尔值填充这个数组 - 最初为每个单元格为 false，然后为 xy 中的每个数字，用 true 填充数组中该数字的倍数的所有条目。

现在对于 ab 中的每个数字，索引到数组模数组长度，如果为真，则跳过，否则如果为假，则返回。

您可以通过从 x 到 y 因子数字中删除其素数扩展是其他数字的素数扩展的严格超集来更快地做到这一点。我的意思是 - 如果你有 2、3、4、5、4 是 2*2 的严格超集 2 所以你可以删除它，现在我们的数组长度只有 30。对于像 3、4、5、6 这样的东西但是，4 是 2*2，6 是 3*2 - 6 是 3 的超集，所以我们将其删除，但 4 不是所有内容的超集，因此我们将其保留。LCM 为 3*2*2*5 = 60 . 做这种事情会给大ab本身带来一些加速，如果你只需要这样做，你可能不需要去阵列方向。

另外，请记住，如果您不打算每次都使用函数的整个结果 - 例如，有时您可能只对最低值感兴趣 - 将其编写为生成器而不是函数。这样你就可以调用它，直到你有足够的号码然后停止，节省时间。

于 2013-04-12T05:35:04.983 回答