Число простых чисел меньше 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