CODEWITHSUNDEEP
c++primesmemsetsieve-of-eratostheneslargenumber
Anand Sasidharan
Anand Sasidharan

Reputation: 21

Prime Number above 6 million

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; 
}

Upvotes: 1

Views: 262

Answers (2)

Deepak Patankar
Deepak Patankar

Reputation: 3302

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.

Upvotes: 3

Ext3h
Ext3h

Reputation: 6393

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.

Upvotes: 3

Related Questions