What could be the reason I am getting segmentation fault using code 1?

Question

Sieve of Eratosthenes method: While I use code 1 to filter prime numbers I get a segmentation fault for an input 16777214, whereas in code 2 it doesn't give a segmentation fault. The segmentation fault comes due to the first 2 lines of code 1 where I define (bool prime) and (memset). What could be the reason I get this fault on https://www.interviewbit.com/problems/prime-sum/

//code 1:
vector<int> Solution::primesum(int A){
    bool prime[A+1];
    memset(prime, true, sizeof(prime));
    for (int p=2;p<=sqrt(A);p++){
        if(prime[p] == true){
            for (int i=p*p;i<=A;i+=p)
                prime[i] = false;
        }
    }
}
````
````

//code 2:
vector<int> Solution::primesum(int A){
    vector<bool> prime(A+1);
        for(int i=2;i<=sqrt(A);i++){
            if(prime[i]==false){
                for(int j=i*i;j<=A;j+=i)
                    prime[j] = true;
            }
        }
}
````
````

Sorry, I changed variable "n" to "A" and data type is int in both cases. — Vince, Jun 08 '19 at 20:34
Both fragments exhibit undefined behavior, by way of accessing an uninitialized variable `A`. The only difference is the manner in which this undefined behavior manifests. — Igor Tandetnik, Jun 08 '19 at 20:35
Your `memset` is not a valid way to set an array of booleans. — molbdnilo, Jun 08 '19 at 20:44
I did an edit 2, both the fragments are part of a function having an argument as int A and return type of vector. — Vince, Jun 09 '19 at 09:40
https://stackoverflow.com/questions/18371584/what-is-the-maximum-size-of-static-array-that-can-be-declared-in-gcc — CaptainDaVinci, Jun 09 '19 at 15:16

CaptainDaVinci · Answer 1 · 2019-06-09T04:59:59.547

0

Assuming the variable A is initialized before creating the array, the memory for the array is allocated on the stack, and because the size of stack is limited, allocating memory for 16777214 bytes can result in stack overflow, which causes a segmentation fault.

Vectors on the other hand are allocated on the heap and the same issue does not occur.

P.S: Variable length arrays is not standard C++, GCC implements them as a non-standard extension.

edited Jun 09 '19 at 04:59

answered Jun 08 '19 at 20:40

CaptainDaVinci

975
7
23

1

It's not because bool vectors are space efficient. It's because vectors allocate their elements on the heap, not the stack. You should also mention that VLAs aren't standard C++. – eesiraed Jun 09 '19 at 00:11

score -1 · Answer 2 · answered Jun 08 '19 at 20:43

-1

Segmentation fault occurs when either array is out of index and you are accessing illegal memory space.

Firstly, array can not be initiated dynamically in this way. You should try this way,

int *prime = new int[length];

Secondly, Maybe for your, prime[n+1] , Your input value exceeded the limit of "n" (int). As you are using data type int and it has it's memory limitation. Try using long int.

answered Jun 08 '19 at 20:43

Muhaimenul Islam

747
1
7
22

Array initialization is correct. Both of the code works for lower inputs. and I have changes variable 'n' to 'A'. In addition, I am clearly asking for input 16777214. – Vince Jun 09 '19 at 09:44

What could be the reason I am getting segmentation fault using code 1?

2 Answers2