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

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; 
} 

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

Answer 1

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

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

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

Некоторые другие замечания, относящиеся к коду:

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

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

Используйте это:

myVector.resize (sz, 1);