Segmentation fault when doing many pushbacks to a vector

Question

I really don't know why I'm having the segmentation fault. I'm trying to generate primes with the code below:

#include <bits/stdc++.h>
using namespace std;

vector<int> prime_list;

void generate_primes(int upper_limit){
    vector<bool> bool_index (upper_limit, true);
    for(int i = 2; i<upper_limit; i++){
        if (bool_index[i]){
            ::prime_list.push_back(i);
            for(int j = i*i; j<upper_limit; j+=i){
                bool_index[j] = false;
            }
        }
    }
}

int main(){
    generate_primes(300000); //for big numbers it gives a segmentation fault
    for(int i: prime_list){
        cout<<i<<" ";
    }
    return 0;*/
}

Any solution?

Answer 1

In your code, there is a overflow in j = i * i when i is 46349. 46349 * 46349 will be too large to be represented in an int (given a 32 bit int). This is a signed integer overflow and it makes your program have undefined behavior. In your case, the result will most probably wrap around at INT_MAX and become -2146737495. This negative index is out of bounds of bool_index, which is also a cause for undefined behavior. A crash is very likely in this case.