爲什麼我的代碼不能正確生成素數

少於10,000,000的素數數目是664,579，但我的代碼只生成664,214。這些數字的來源是https://primes.utm.edu/howmany.html 爲什麼我的代碼不能正確生成素數

#include <iostream> 
#include <bitset> 
#include <vector> 
using namespace std; 

const int N = 10000001; 
bitset<N>num; 
vector<int>prime; 
inline void sieve() 
{ 
    num.flip(); 
    num[0] = num[1] = 0; 
    for(int i=2;i<N;i++) 
     if(num[i]) 
     { 
      prime.push_back(i); 
      for(long long unsigned j=i*i; j<N;j+=i) 
       num[j] = 0; 
     } 
} 

int main() { 
    sieve(); 
    cout << prime.size() << endl; 
    return 0; 
}

來源

2014-11-04 MNT.95

計算i*i當你有一個整數溢出。然後將結果分配給long long的事實不會使編譯器在乘法之前提升類型。

如果我聲明i作爲long long unsigned int那麼你的程序輸出664579

來源

2014-11-04 12:35:55

如果j'的'初始化被改變爲'J =（無符號長長）我* i'，也打印正確的輸出。 – hvd 2014-11-04 12:36:43

如果外環的限制設置正確（對於sqrt（N）），那麼乘法永遠不會溢出。這不僅是盡職調查，它還將外循環的迭代次數減少到一小部分。注意：根據四捨五入模式，'sqrt（）'可以向上取整而不是向下取整;最好寫一個小函數'max_factor（）'，它可以處理血腥細節，並且可以單獨測試。 – DarthGizka 2014-11-04 13:27:16

對於通常的篩碼，如果使用正確的數據類型（無符號整數），邊界情況的數量大大減少，如果使用打包（僅賠率）位圖，則會更多，因爲這會在索引中購買額外的頭位空間變量。在一個問題中不必要地拋出雙寬整數並不是一種可能導致良好和健壯的代碼的策略;除了鼓勵知識分子的懶惰之外，它還會使代碼更加混亂而不是更好。 – DarthGizka 2014-11-04 13:34:15

爲什麼我的代碼不能正確生成素數

回答

相關問題