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

Question

这是我一直在思考的一段时间的问题。

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

考虑一下：

我想找到所有没有被2整除至5 这个过程的数字从1到10会变得非常慢，如果我在那里用线性的方法; 像这样：

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整除。因此，更快的方法是计算你感兴趣的范围内的素数，然后简单地计算它们划分的值。

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

如果我们结合这两种方法，我们看到我们可以创建所有值的set（因此在本示例中，所有值为1到10的集合），并且只需删除第二范围中每个素数的倍数从那套。

编辑：正如Patashi指出的那样，如果分割一个给定值的素不在集合中，这将不会起作用。为了解决这个问题，我们可以应用类似的算法：创建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秒钟。

Answer 2

终极优化警告：不要过早地优化。无论何时您尝试优化代码，对其进行配置以确保它需要优化，并根据您希望优化的相同类型的数据来优化优化，以确认其速度。几乎所有的代码都不需要优化，只是为了给出正确的答案。

如果在优化小的x-y和大的A-B：

创建具有长度的数组，它是最小公倍数出所有的x的，X + 1，X + 2 ... Y。例如，对于2,3,4,5，它将是60，而不是120.

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

现在在A-B每一个数字，指数进入阵列模arraylength，如果这是真的，否则跳过如果是假的，回报。

您可以通过从您的x中移除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 。做这样的事情会给大型自动驾驶仪带来一定的加速，如果这就是你需要的，你可能不需要走阵列方向。

另外，请记住，如果你不打算使用该函数的整个结果每一次 - 样，也许有时你只能在最低值兴趣 - 它写成一台发电机，而不是一个函数。这样，您可以调用它，直到您有足够的数字，然后停止，节省时间。