查找從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 。做這樣的事情會給大型自動駕駛儀帶來一定的加速，如果這就是你需要的，你可能不需要走陣列方向。

另外，請記住，如果你不打算使用該函數的整個結果每一次 - 樣，也許有時你只能在最低值興趣 - 它寫成一臺發電機，而不是一個函數。這樣，您可以調用它，直到您有足夠的數字，然後停止，節省時間。