最有效的方法來找到兩個數字的公約數達10^6

我想存儲所有數字從1到10^6的所有除數。但是這似乎太慢了。這是我的代碼的預處理（）函數：最有效的方法來找到兩個數字的公約數達10^6

for(int i=1; i<=1000000; i++) 
{ 
    for(int j=1; j<=i/2; j++) 
    { 
     if(i%j==0) 
      divi[i][j] = true; 
    } 
}

我用這樣的地圖容器：

map <int, bool> divi[1000010];

然後我試圖找到兩個給定數字的公約數。

preprocess(); 

int T, A, B; 

cin >> T; 

while(T--) 
{ 
    cin >> A >> B; 

    int common = 0; 
    for(it = divi[A].begin(); it!=divi[A].end(); it++) 
    { 
     if(divi[B][it->first]==true) 
      common++; 
    } 

    cout << common << endl;

現在應該如何使它足夠快？

來源

2016-11-02 BlackBeard

看看[Euclidean_algorithm]（https://en.wikipedia.org/wiki/Euclidean_algorithm） – Jarod42

請注意'divi [B] [it-> first] == true'會創建一個新的地圖條目，如果不存在的話。這變得非常昂貴，特別是對於素數。 – molbdnilo

順便說一句，'std :: map '可能會被替換爲'std :: set '。 – Jarod42

除了使用std::map的事實本身很昂貴（不能使用數組嗎？），快速數值贏只能達到內循環中數字的平方根。

for (int j = 1; j * j <= i; j++)

（注意到平方j比計算便宜的i的平方根，並保持你遠離浮點計算。）

這必須加上指出，如果j是一個除數，則i/j是也是除數。所以，你還需要

divi[i][j] = divi[i][i/j] = true;

這種優化是圍繞單數的約數的計算爲中心，以取代

divi[i][j] = true;

。有更快的方法來獲取集合的數字，但我的方法可能就足夠了。如果不是，請下降。

來源

2016-11-02 08:41:50 Bathsheba

這取決於你想要什麼：如果你只想要一些特定數字的公約數，那麼歐幾里德算法就是解決方案。

如果你真的想所有數字1..1所有分頻器的列表，一個解決辦法是（類似於篩）：

for(int I=1;I<=sqrt(n);++I) { 
    for(int j=I;j*I<=n;++j) divi[I*j][j]=divi[I*j][I]=true; 
    }

原來的代碼複雜度爲O（N^2）第一個答案是O（N^1.5）。我相信新的公式是O（N * log N）

來源

2016-11-02 09:03:18

當然，您可以使用I * I <= n而不是I <= sqrt（n）;正如其他答案中所建議的。 –

最有效的方法來找到兩個數字的公約數達10^6

回答

相關問題