如何更快地創建以下C++程序？

-3

鏈接的問題 - https://www.hackerrank.com/contests/freshers-challenge-2/challenges/counting-the-steps 如何更快地創建以下C++程序？

的問題如下 - （包括A和B，在情況下，他們都是素）找到A和B之間的素數的數量

我用的篩子Eratosthenes解決了這個問題，但是我在兩個測試用例中超時。

特別是對於一個測試用例，其中有10,000個數字，我的C++程序在CodeBLocks中花費了大約10秒。我在下面插入代碼段 -

for(int i=2;i<=upperbound;i++) 
{ 
    prime[i-2]=i; 
} 
int sq=sqrt(upperbound); 
for(int i=0;prime[i]<=sq;i++) 
{ 
    if(prime[i]!=0) 
    { 
     int j=i+prime[i]; 
     for(;j<m;j+=prime[i]) 
     { 
      prime[j]=0; 
     } 
    } 
}

這是篩網的代碼片段。我的輸出都是正確的，但我怎樣才能讓這個程序更快。

編輯：段故障被解決了平

來源

2015-03-31 tech96

你正在計算'sqrt'（可能很貴），並沒有真正使用它。 – TZHX 2015-03-31 12:16:40

幾件事情：你定義'sq'，但似乎沒有使用它;你使用'm'但是不要定義它（在你所包含的代碼片段中）。另外，如果其中一個測試案例導致seg-fault，則輸出不能「全部正確」。您應該可能會顯示更多的代碼和導致問題的測試用例。 – TripeHound 2015-03-31 12:17:01

這看起來不像Eratosthenes的篩子給我。看看在這裏的僞代碼：http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Implementation – NathanOliver 2015-03-31 12:18:44

唯一一次吞我在你的代碼中看到替換上界後使用sqrt。您可以使用digit by digit method in base 2。

但這是一個小改進。

您必須更改算法才能獲得更好的結果。素數的搜索是一個困難的問題，有很多的至少最壞解決方案（例如，你可以使用pseudo-prime filters ......）

來源

2015-03-31 12:21:49 Orace

通常的解決方法是用'x <0 ||代替'x 0'，所以替換的前半部分甚至不需要。 – MSalters 2015-03-31 15:29:43

~~您正在使用sqrt，這可能是耗時的，特別是因爲它找到雙重根。之後您甚至不使用sq。~~

編輯：嘗試在您的循環中用sq代替upperbound。它會解決一些速度問題，但不是segfault，這可能是分配過大內存的結果。

篩選算法的問題是它爲所有數字分配完整數組。

找到質數的另一種方法是通過將質數除以它們的平方根來檢查所有數字。該算法的簡單優化是避免偶數。並存儲只有結構中的素數。

int lastBound = 0; //avoids doing too many multiplications 
vector<int> primes; 

primes.push_back(2); 

for (int i = 3; i <= upperbound; i+= 2) { 
    bool prime = true; 
    for(int j : primes) { 
     if (j > lastBound && j * j > i) { 
      lastBound = j; 
      break; 
     } 

     if (i%j == 0) { 
      prime = false; 
      break; 
     } 
    } 

    if (prime) { 
     primes.push_back(i); 
    } 
}

然後，你有列表中的素數，你可以將它轉換爲像你有一個數組，或一組。

有一些動態分配會導致一些延遲，但對於大小爲n的vector，只有O（log（n））分配。可能會進一步優化，但爲了您的目的，它應該足夠了。

來源

2015-03-31 12:22:06 coyotte508

@ g24l'emplace_back'只有在'vector'包含一個以'int'作爲其非複製構造函數參數的類時纔有用，這裏與'push_back'相同。 – coyotte508 2015-03-31 12:30:32

'foreach（int j，primes）'？ – 2015-03-31 12:40:26

@ 1nflktd：對不起，也習慣了Qt，我的意思是'for（int j：primes）'。 – coyotte508 2015-03-31 12:47:06

您在數組中有效地存儲質數兩次。 prime[i] == i+2，所以你可以用int j=i+(i+2);代替int j=i+prime[i];。

現在，如果您不再需要實際值，則可以只存儲一個位：std::vector<bool> prime(upperbound, true);。這將內存需求減少了95％（可能），這使得篩選可能適合CPU緩存。

在prime開頭保存2位是個不錯的主意。其他地方的單個指令將佔用至少一個完整的字節，並且還會耗費實際的運行時間。

來源

2015-03-31 15:48:50 MSalters

如何更快地創建以下C++程序？

回答

相關問題