Prime Number above 6 million

Question

I was solving a question in Hackerrank and the question was to find the prime number count in a range. Since using the normal methodology was facing timeout, I used Sieve of Eratosthenes. Most testcases worked except two hidden testcases. I ran the code in a GDB compiler and figured out that the code only supports values upto 6 million. What do I do? The code is given below:

#include<cstring>
#include<cstdio>
#include <iostream>
#include <algorithm>
using namespace std;


void SieveOfEratosthenes(unsigned long long int a,unsigned long long int b) 
{ 
    unsigned long long int count=0; 
    bool prime[b+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (unsigned long long int p=2; p*p<=b; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            for (unsigned long long int i=p*p; i<=b; i += p) 
                prime[i] = false; 
        } 
    } 
  
    for (unsigned long long int p=a; p<b; p++) 
       if (prime[p] &&p!=1) 
           count++;
    cout<<count;
          
} 
  
int main() 
{ 
    unsigned long long int a,b;
    cin>>a>>b;
    SieveOfEratosthenes(a,b); 
    return 0; 
}

maybe not *the* problem, but `bool prime[b+1];` is not standard c++. [Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) — 463035818_is_not_an_ai, Aug 03 '20 at 09:24
Maybe you are overflowing the function stack, you can use vector in place of bool array `bool prime[b+1]; ` — Deepak Patankar, Aug 03 '20 at 09:27
An array of size 6mln of bools (each of size 1 byte) is about 6Mb of stack size. You are almost surely above stack limit. — freakish, Aug 03 '20 at 09:30
One thing I wanna ask : Do you have to answer multiple queries containing `a` and `b`? — brc-dd, Aug 03 '20 at 09:43
Try `bool prime[b+1]` -> `static bool prime[b+1] `. If it works, then it's a stack size problem as mentioned in preceeding comments. — Jabberwocky, Aug 03 '20 at 09:50

score 3 · Answer 1 · answered Aug 03 '20 at 09:28

Looks like a classic stack overflow. bool prime[b+1]; is allocated on stack, and you have hit a limit.

If this is running on Linux, then the maximum allowed stack size is typically around 8MB in total or less, so there is a good chance you just exceeded that.

Move it off the stack, or perform bitpacking rather than full bool and it should work just fine again.

score 3 · Answer 2 · answered Aug 03 '20 at 09:34

3

You are creating a bool array in your function, which will be stored on the stack. On Windows, the typical maximum size for a stack is 1MB, whereas it is 8MB on a typical modern Linux. You are creating an array with 6million records which will be nearly 6MB.

To solve this problem you can create a vector instead of the array, which will be stored in heap.

answered Aug 03 '20 at 09:34

Deepak Patankar

3,076
3
16
35

minor nitpick: The vector can be on the stack, but its data is on the heap – 463035818_is_not_an_ai Aug 03 '20 at 09:52
1

`vector` may have some minor issues because it's the only "packed" vector class, but in this case that's a benefit. It will be only 750 kB for 6 million bools, and indeed vector itself will allocate that 750kB from the heap. – MSalters Aug 03 '20 at 10:33
Thanks @idclev463035818 for the suggestion, I have added a link which explains the concepts you are referring to deeply. – Deepak Patankar Aug 03 '20 at 11:15
Thanks @MSalters, I didn't understand how it will take only 750kB, Can you please explain ? – Deepak Patankar Aug 03 '20 at 11:18
@DeepakPatankar: `std::vector` doesn't have an internal representation as `bool[]`, which is why `std::vector::data()` is missing. Instead, it stores 8 bools per byte. 6 million / 8 = 750.000. – MSalters Aug 03 '20 at 11:21

Prime Number above 6 million

2 Answers2