SIGSEGV with an extremely large array in C++ loop

Question

The following code that prints some primes using sieve generates SIGSEGV error on an online judge.

int main()
{
long count=1;
int arr[100000000];
printf("2\n");
for(long i=3;i<100000000;i=i+2)
{
    arr[i]=1;
}
for(long i=3;i<100000000;i=i+2)
{
    if(arr[i]==1)
    {
        count++;
        if(count%100==1)printf("%ld\n",i);
        for(long j=2;i*j<100000000;j++)
            arr[i*j]=0;
    }
}
//scanf("%ld",&count);
}

but if I remove some statements as:

for(long i=3;i<100000000;i=i+2)
{
    if(arr[i]==1)
    {
        count++;
    }
}

modify the second loop as above. it doesn't show the error. Could some help as to why this occurs and how to correct this int the first program.

Answer 1

This is almost certainly a stack overflow, caused by declaring an enormous automatic array. Automatic variables are typically placed on the stack, which typically has a maximum size of the order of a few megabytes.

You can fix it by using a dynamic array, typically allocated on the heap:

std::vector<int> arr(100000000);