我昨天讀了關於Eratosthenes的Sieve並想實現它

我正在尋找一些關於我的算法實現的反饋。我該如何改進它？當計算由於整數溢出而產生的大質數> 46349時遇到了問題，但通過使用sqrt而不是pow解決了這個問題。我昨天讀了關於Eratosthenes的Sieve並想實現它

#include<iostream> 
#include<math.h> 
using namespace std; 

int main(){ 
    int number; 
    cin >> number; 
    const int CAP = number; 
    bool * prime = new bool[CAP]; 

    for(int i = 0; i <= CAP; i++){ //sets all to true for the marking 
     prime[i] = true; 
    } 

    for(int i = 2; i <= number; i++){ 
     if(i <= sqrt(number) && prime[i] == true){ 
      for(int j = i*i; j <=number; j++){ //if %i == 0 mark false 
       if(j % i == 0){    //haven't tried another way 
        prime[j] = false; 
       } 
      } 
     } 
    } 

    for(int i = 2; i <= number; i++){ 
     if(prime[i] == true){ 
      cout << i << endl; 
     } 
    } 

    return 0; 
}

來源

2014-03-31 Lanyard

這個問題似乎是題外話題，因爲它是關於審查（工作？）的代碼。 – user2864740

stackoverflow適用於有錯誤的代碼，但一定要解釋你得到的問題，因爲人們不喜歡只編碼並且不得不猜測。 –

嘗試在codereview.SE，他們更偏向於這樣的問題。 – Sinkingpoint

你訪問數組越界在：

bool * prime = new bool[CAP]; 

for(int i = 0; i <= CAP; i++)

，你應該改變它使用<代替<=

注意，同樣適用於你的其他的<=也循環。

來源

2014-03-31 21:51:15

我做了這些更改。謝謝！ – Lanyard

除了修復您在所有循環中獲得的數組超出範圍的錯誤（使用i <長度，而不是i < =長度），您還可以執行幾項有效工作。首先，您可以在數組上使用memset將其中的所有內容設置爲true。另外，你的inner for循環（用j作爲變量）做了額外的東西，它不需要;而不是檢查每個j是否j％i == 0，只需用j + = i替換j ++，這樣j總是可以被i整除。較少的優化是改變你的外部循環的邊界（我< = sqrt（數字），所以你不需要在內部循環之前的if語句）

來源

2014-03-31 22:06:21 Straw1239

你實際上可以完全消除sqrt。有：

if(i <= sqrt(number) && prime[i] == true) {

，但首要條件是多餘的下一行，其中i*i相比number

for(int j = i*i; j <= number; j++) {

所以先變成只是

。

if (prime[i]) {

來源

2014-03-31 22:10:57

我昨天讀了關於Eratosthenes的Sieve並想實現它

回答

相關問題