run time error (SIGSEGV) SPOJ Sieve of Eratosthenes [closed]

Question

Closed. This question needs debugging details. It is not currently accepting answers.

---

Edit the question to include desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem. This will help others answer the question.

Closed 7 years ago.

Improve this question

Hi I'm getting SIGSEGV error for this problem, dont know where is th problem: http://www.spoj.com/problems/PRIME1/ I tried to solve it by sieve-of-Eratosthenes algo given on Wikipedia. here is my code, please help thanks in advance.

int main()
{
   int t;   // test cases

   cin>>t;

   while(t--)
   {
      long int m,n;
      cin>>m>>n;


      if( 1 <= m <= n <= 1000000000 && n-m<=100000)
      {
         bool a[n];
         for(long int i=2;i<=n;i++)
         {
            a[i]=true;  // set all to true
         }
         a[0]=false;
         a[1]=false;
         for( long int i=2;i*i<=n;i++)
         {
            if(a[i])
            {
               for( long int k=i*i;k<=n;k+=i)
               {
                  a[k]=false;
               }
            }
         }
         for(long int i=m;i<=n;i++)
         {
            if(a[i])
               cout<<i<<endl;         //Now all i such that a[i] is true are prime.
         }
         cout<<endl;
      }
      else
         return -1;
   }

   return 0;
}

Answer 1

There are 3401 primes below the square root of 10⁹. That's all you need to sieve any segment of numbers below the 10⁹ upper limit.

So, first, sieve a segment from 2 to 31622. Store the resulting 3401 prime integers in an array.

Then for each pair of numbers m <= n, m >= n - 100000 create a temporary array covering the segment from m to n inclusive, and sieve it with those primes you've calculated in the first step. You can stop each sieving when a prime's square is above a given n:

for( i=0; primes[i]*primes[i] <= n; ++i)
{
    ....

See also my posts about the "offset sieve" of Eratosthenes.

Answer 2

You have to use gdb to find out exactly what happened. There are many things wrong with this code.

1. As pointed out in the comments, for n large enough your a[n] will overflow the stack.

2. You have an off-by-one error in your first and third for loops; you check a[n] but only allocated up to a[n-1]. All of the i <= n should be i < n

3. if( 1 <= m <= n <= 1000000000 && n-m<=100000) is probably not what you intended; for any positive integer 'n', (1 <= m <=n) will be true

Answer 3

This problem has been treated before on SO. For example, see Sieve of Eratosthenes on Stack Overflow. You may also want to read this blog that describes a typical C implementation: C implementation of Sieve of Eratosthenes. As pointed out above there are multiple issues with your code, so many in fact that you need to think about reorganizing it completely. Please read the linked posts to get ideas for how to do that successfully.