小于 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;
}
最佳答案
计算 i*i
时出现整数溢出。您随后将结果分配给 long long 的事实不会使编译器在乘法之前提升类型。
如果我将 i
声明为 long long unsigned int
那么您的程序输出 664579
关于c++ - 为什么我的代码不能正确生成质数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26735083/