Limit on array size

Question

I wrote the following code in c++ which was supposed to print as well as calculate all the prime numbers till n. The code is perfectly working for n<=10000 but is not working for n>=100000.

#include "iostream"
#include "vector"
using namespace std;
int main(){
    int n,ans=0;
    cin>>n;
    vector <bool> v(n+1,true);
    for(int i=2;i<=n;i++){
        if(v[i]){
            cout<<i<<endl;
            ans++;
            for(int j=i*i;j<=n;j+=i)
                v[j]=false;
        }
    }
    cout<<endl<<ans;
    return 0;
}

Kindly state the reason. Thank you.

Answer 1

In your inner look, j=i*i will overflow a 32-bit signed integer at around 46341. The easiest fix there is to use a long long for j and also cast i correctly before multiplication.

So, change the inner loop to

for (auto j = static_cast<long long>(i) * i; j <= n; j += i)

And that should be it.

As a side note, please don't #include standard headers with double quotes; prefer <vector> and <iostream>.

UPDATE: As a more robust way of doing the same thing (and still using roughly the same code,) I'd suggest the following:

#include <iostream>
#include <vector>
using namespace std;
int main(){
    size_t n, ans = 0; // A) Switch to size_t, which can accommodate the largest
                       //    size of a vector; if your number is larger, then we
                       //    can't make an array for it... 
    cin >> n;
    vector<bool> v (n, true); // B) Remove the chance of overflow; indices are
                              //    now shifted by one
    for(size_t i = 2; i <= n; i++) {
        if (v[i - 1]) {
            cout << i << endl;
            ans++;
            if (n / i >= i) { // C) Check for possibility of overflow in `i*i`
                
                // D) Switch j to correct type
                // E) Check if `j+=i` overflowed
                for (size_t j = i * i; j <= n && j > i; j += i)
                    v[j - 1] = false;
            }
        }
    }
    cout << endl << ans;
    return 0;
}

The really important changes are A, C, and D. The other two, B and E are needed for complete correctness, but they only matter when you have enough actual memory in your system to almost overflow size_t (otherwise, the ctor for vector would throw.) This is completely probably on 32-bit systems, but impossible on 64-bit builds for now.

Also note that A, B, and D are "essentially" free (perf-wise,) but C and E do have some impact on running time (although probably tiny; E is the more onerous.)