Почему мой код не генерирует простые числа правильно

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

0

Решение

У вас есть целочисленное переполнение при расчете i*i, Тот факт, что вы затем присваиваете результат long long, не заставляет компилятор продвигать типы перед умножением.

Если я заявляю i как long long unsigned int тогда ваша программа выводит 664579

4

Другие решения


По вопросам рекламы [email protected]