查找从a到b的数字不能被x到y整除

Question

这是我一直在思考的一个问题.

查找从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都是如此

Answer 1

您只需要检查可能除数范围内的素数 - 例如，如果一个值不能被 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 秒。