Eratosthenes的篩子與範圍

-1

我試圖生成從N到N_Max在C++中開始的素數序列。我的方法是使用埃拉托色尼的篩生成這些素數：Eratosthenes的篩子與範圍

void runEratosthenesSieve(int upperBound) { 
     int upperBoundSquareRoot = (int)sqrt((double)upperBound); 
     bool *isComposite = new bool[upperBound + 1]; 
     memset(isComposite, 0, sizeof(bool) * (upperBound + 1)); 
     for (int m = 2; m <= upperBoundSquareRoot; m++) { 
      if (!isComposite[m]) { 
        cout << m << " "; 
        for (int k = m * m; k <= upperBound; k += m) 
         isComposite[k] = true; 
      } 
     } 
     for (int m = upperBoundSquareRoot; m <= upperBound; m++) 
      if (!isComposite[m]) 
        cout << m << " "; 
     delete [] isComposite; 
}

但是這個功能浪費內存通過計算質數1到N是否有運行速度更快，佔用內存更少的功能？

來源

2015-04-05 Jese Rodrigues

您可能會喜歡我對[此問題]（http://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes）的回覆，它只會生成給定範圍內的素數。 – user448810 2015-04-05 16:22:34

它在phyton中，我會嘗試翻譯，但謝謝你！ – 2015-04-05 18:54:37

它實際上不是Python，而是一種僞代碼。 – user448810 2015-04-05 18:56:29

您只需確定最大值爲sqrt(N_max)的值是素數還是複合數值 - 就像您已經在做的那樣。然後從N循環到N_max，並確定每個值是否可以被發現的素數（在2和sqrt(N_max)之間）整除。

這隻會是你的方法的一個小調整。

的一旁：而不是使用浮點計算平方根（即sqrt()），有用於計算「整數平方根」簡單的算法（即，給定的值M，找到該值R這是最大的整數例如R*R <= M）。輕鬆找到使用您最喜愛的搜索引擎。優點是它可以讓你遠離浮點細節，並且不得不將其轉換爲整數。

來源

2015-04-05 11:38:36 Peter

Eratosthenes的篩子與範圍

回答

相關問題