为什么我的代码不能正确生成素数

少于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

为什么我的代码不能正确生成素数

回答

相关问题