C++ Coprimes問題。優化代碼

嗨，我想優化下面的代碼。它試圖通過將它們與n進行比較來查找給定範圍內的所有coprimes。但我想讓它跑得更快......有什麼想法？C++ Coprimes問題。優化代碼

#include <iostream> 

using namespace std; 

int GCD(int a, int b) 
{ 
    while(1) 
    { 
     a = a % b; 
    if(a == 0) 
    return b; 
    b = b % a; 

     if(b == 0) 
    return a; 
    } 
} 


int main(void){ 
int t; 
cin >> t; 
for(int i=0; i<t; i++){ 
    int n,a,b; 
    cin >> n >> a >> b; 

    int c = 0; 
    for(int j=a; j<=b; j++){ 
    if(GCD(j, n) == 1) c++; 
    } 

    cout << c << endl; 
} 

return 0; 
}

來源

2010-09-11 richardalberto

這味道就像做家庭作業，所以只有一個提示。

這裏不需要計算GCD。如果你能分解n（即使以最簡單的方式試圖除以每個小於2^16的奇數），那麼你可以計算不會被n因子分割的數字。

請注意，一個32位數最多隻能有10個因子（我們不需要記住在因子分解中使用了素數的次數）。

如何做到這一點？嘗試使用包含 - 排除原則來計算非副本。您最多隻能檢查1023個質數子集，對於每個子集，您需要計算該範圍內有多少倍數，這是每個子集的恆定時間。

不管怎樣，我的代碼在任何時間，現在工作：

liori:~/gg% time ./moje <<< "1 1003917915 1 1003917915" 
328458240 
./moje <<< "1 1003917915 1 1003917915" 0,00s user 0,00s system 0% cpu 0,002 total

來源

2010-09-11 22:51:49 liori

不，這不是功課......大聲笑...我爲今年的ICPC留下了印象。但是謝謝你的提示。一旦我測試它，我會盡快通知你。 :) – richardalberto 2010-09-12 05:18:31

在一臺核心計算機上，它不會比現在快得多。所以你想利用多個核心甚至多個計算機。並行化和分發。

由於每對想要計算GCD的數字都沒有鏈接到任何其他數字對，所以您可以輕鬆地修改程序以通過使用線程來利用多個核心。

如果仍然不夠快，最好開始考慮使用分佈式計算，將工作分配給多臺計算機。這有點棘手，但如果搜索空間很大，應該提高性能。

來源

2010-09-11 22:01:00

如何使用線程？ – richardalberto 2010-09-11 22:25:21

@RichardGonzálezAlberto：看看Boost :: Thread http://www.boost.org/doc/libs/1_44_0/doc/html/thread.html – 2010-09-11 22:28:48

謝謝，但這對我不起作用，我需要來自標準C++庫的東西。不能使用外部庫。 – richardalberto 2010-09-11 22:34:40

考慮試試double s。它表示，在典型的英特爾芯片上，雙打分區速度更快。整數除法是那裏最慢的指令。這是一個雞蛋問題。沒有人使用它們是因爲它們速度慢，而且英特爾沒有使它更快，因爲沒有人使用它。

來源

2010-09-11 22:14:15

我可以用％打雙打嗎？ – richardalberto 2010-09-11 22:25:37

您不能使用'％'運算符，但'fmod'函數執行同樣的操作。 – 2010-09-11 23:22:56

我會試試這個。謝謝。 – richardalberto 2010-09-12 05:19:30

C++ Coprimes問題。優化代碼

回答

相關問題