Создание сита с векторами

Question

Создание сита с векторами

Я пытаюсь сделать простое сито с векторами:

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

vector<int> myVector;

void vec_sieve()
{
myVector.push_back(0);
myVector.push_back(0);

unsigned int sz = pow(2,31);
for(unsigned int i=2;i<sz;i++)
{
myVector.push_back(1);
}

int len = sqrt(sz);
for(unsigned int i=2;i<=len;i++)
{
if(myVector[i] == 1)
{
for(unsigned int j=2;i*j<=sz;j++)
{
myVector[i*j] = 0;
}
}
}
}

int main()
{
vec_sieve();
int n;
cin>>n;
unsigned int input;

for(int i=0;i<n;i++)
{
cin>>input;
if(myVector[input] == 1)
{
cout<<"Prime"<<endl;
}
else
{
cout<<"Not Prime"<<endl;
}
}

return 0;
}

Я новичок в vector и пытаюсь создать векторы простых чисел с помощью seive, но каким-то образом я получаю Bad_Alloc
Кто-нибудь может быть конкретно об этом плохом распределении?
заранее спасибо

-1

c++sieve vector

Решение

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

Других решений пока нет …

Источник

Accepted Answer

std::bad_alloc вероятно, выброшен, потому что вы пытаетесь выделить непрерывный блок памяти в виртуальной памяти, который слишком велик, чтобы поместиться в любой из его «пробелов».

unsigned int sz = pow(2,31); // too large

2 ^ 31, умноженный на 4 байта (размер целого), равен 8 ГБ. Вы всегда должны сначала думать о том, «сколько памяти он выделяет», когда дело доходит до определения размеров массивов.
Кроме того, bool достаточно для того, чтобы содержать 1 и 0. vector<bool> оптимизирует память еще больше.

Некоторые другие наблюдения, связанные с вашим кодом:

Вместо этого:

for(unsigned int i=2;i<sz;i++)
{
myVector.push_back(1);
}

Использовать этот:

myVector.resize (sz, 1);

1