How to fix runtime error on sieve, the runtime error is signed integer overflow: 46349*46349?

Question

When I'm trying to use sieve, it gives me "runtime error: signed integer overflow: 46349 * 46349 cannot be represented in type 'int'" for long long int j = i*i; line.. but the variable j is already long long int, not int, why is it still gives me error?

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

bool Eliminated[1000001];
int N;

void Sieve(){
    Eliminated[1]=true;
    for(int i = 2;i<=1000000;i++){
        if(Eliminated[i]==false){
            long long int j = i*i;
            while(j<=1000000){
                Eliminated[j]=true;
                j=j+i;
            }
        }
    }
}

int main(){
    Sieve();
    cin>>N;
    long long int arr[N];
    for(int i = 0;i<N;i++){
        cin>>arr[i];
        long long int temp = sqrt(arr[i]);
        if(temp*temp==arr[i]){
            if(Eliminated[temp]==false){
                cout<<"YES"<<endl;
            }else{
                cout<<"NO"<<endl;
            }
        }else{
            cout<<"NO"<<endl;
        }
    }
}

Does this answer your question? [Long integer overflow in C++](https://stackoverflow.com/questions/44874465/long-integer-overflow-in-c) Though you have a variable here instead of a literal, it's the same principle: the type of the expression is not determined by its context, but the expression itself: just `i*i` here. — harold, Feb 27 '20 at 15:00

score 1 · Accepted Answer · answered Feb 27 '20 at 15:02

For type "long long" there is a stated minimum length requirement - A long long int must be at least as long as a "long". This is not being met at every iteration within the loop (2*2 = 4 does not meet the minimum requirement).

Feel free to see this page for more details.

What is the difference between "long", "long long", "long int", and "long long int" in C++?

How to fix runtime error on sieve, the runtime error is signed integer overflow: 46349*46349?

1 Answers1