Sigsegv error even after using segmented sieve of Eratosthenes

general
, , ,
1

I am getting a sigsegv error in SPOJ Prime1 problem even after using segmented sieve of eratosthenes
http://www.spoj.com/problems/PRIME1/

#include<iostream>
#include<cmath>
using namespace std;

int main()
  {
   int prime[100000];
   int myprime[100000];
   long long int m,n,i,j,q,s,r,w,p;
   int t,range;
   cin>>t;
   while(t--)
     {
        r=0;

       cin>>m>>n;
       range=floor(sqrt(((double)n)));
       prime[0]=0;
       prime[1]=0;
       for(i=2;i<=n;i++)
        prime[i]=1;

       for(i=2;i<=range;i++)
       {

       if(prime[i]==1)
          {
          for(j=2;i*j<=n;j++)
              {

                prime[i*j]=0;
              }

          }
       }

       for(i=2;i<=n;i++)
          {

          if(prime[i]==1)
             {
             myprime[r]=i;
             r++;
             }
          }

        for(i=0;i<r;i++)
        {

           w=m/myprime[i];         
           w=w*myprime[i];             
           p=myprime[i];

           for(s=w;s<=n;s=s+p)   
              {

              if(prime[s]==1)
                 {
                 for(q=2;s*q<=n;q++)    //possible bug
                    {
                    prime[s*q]=0;
                    }
                 }
              }
         }

         for(i=m;i<=n;i++)
         {
           if(prime[i]==1)
           {
               cout<<i<<"\n";

           }
         }
       cout<<"\n";


      }




       return 0;

        }
2

You have written:

for(int i = 2 ; i <= n ; i++)
    prime[i] = 0;

What if n is greater than 10^{5}? The size of array prime is only 10^{5} so you are trying to index an element which does not exist, thus segmentation fault.

Edit 1: My solution

We know that a number N is a prime if it is not divisible by any number in the range [2, \sqrt{N}]. Extending this statement, we can say that any number between [2, 10^{9}] will be a prime number if it is not divisible by any number in the range [2, \sqrt{10^{9}}] which is equal to [2, 31624] (approximately). We can find all the prime numbers in this range easily using Sieve of Eratosthenes. Do this and store all prime numbers in this range in an array. Now, you can use this array to find all prime numbers in any range [m, n].

Edit 2:

Let’s assume a test case: m = 2, n = 24

First, we will make an auxiliary array to represent all numbers in the range [m, n] (note that in the question it is given that n-m<=10^{5}, so we can do this without fear of segmentation fault). In this array, we will strike out the multiples of all prime numbers (pk where p is a prime number less than or equal to \left \lfloor \sqrt{n} \right \rfloor and k > 1) and the remaining numbers will be prime in that range. ex:

2 \ \ 3 \ \ 4 \ \ 5 \ \ 6 \ \ 7 \ \ 8 \ \ 9 \ \ 10 \ \ 11 \ \ 12 \ \ 13 \ \ 14 \ \ 15 \ \ 16 \ \ 17 \ \ 18 \ \ 19 \ \ 20 \ \ 21 \ \ 22 \ \ 23 \ \ 24

Removing all numbers of the form 2k where k > 1, this will become:

2 \ \ 3 \ \ 5 \ \ 7 \ \ 9 \ \ 11 \ \ 13 \ \ 15 \ \ 17 \ \ 19 \ \ 21 \ \ 23

Removing all numbers of the form 3k, where k > 1, this will become:

2 \ \ 3 \ \ 5 \ \ 7 \ \ 11 \ \ 13 \ \ 17 \ \ 19 \ \ 23

Here, we check that \left \lfloor \sqrt{24} \right \rfloor = 4 and we have removed factors of all prime numbers less than or equal to 4. The remaining numbers are all prime numbers. In this way we can solve it for any given [m, n].

You can optimise the way in which you struck out the numbers. One naive way is to iterate through the array for every prime number (<=\left \lfloor \sqrt{n} \right \rfloor) and strike out the numbers which satisfy the condition. An optimised way will be to do some computation to calculate the first number that needs to be struck and the advance the array with i += p instead of i++. I was able to achieve a minimum time of 0.09 secs.

1 Like
3

could you suggest an alternative as I can’t increase the array size as it is maximum possible

4

What do you mean by “maximum possible”? You should be able to allocate much larger arrays than 10^5 (either globally or dynamically). If you mean that you can’t go up to 10^9 you’re right.

5

@ceilks -I meant that I can’t go upto 10^9
and @shubhambhattar -I coded it but it is not working
https://ideone.com/ig3vus

6

@artist Can you elaborate what problem you are facing (WA, TLE, SIGSEGV) or if you know a particular case where your code is giving wrong answer then give it. Also, I noticed one thing in your code, you are calculating the prime numbers in each test case, you don’t need to do that. That is redundant work and will unnecessarily increase running time of your program. You should do it only once, probably before the loop “while(t–)” and use it in each test case.
Edit: Also put more comments as it will be easier to understand.

7

I am getting a sigsegv error ,also my logic is incorrect

8

Line no. 30 is where your code is giving segmentation fault. Suppose i = 2, then the maximum value that j will attain in your loop will be n/2 and i*j can go upto n. Size of array prime is 10^5 and for large values of n (like 10^9), your code will try to index an element which does not exist. That will give Segmentation Fault. Check this out: IwMUtS - Online C++ Compiler & Debugging Tool - Ideone.com . variable j cannot go greater than 12774.

9

I changed my code actually the problem is in the code-snippet which marls offsets in the range and I am unable to figure out the logic to do it https://ideone.com/Ryhi9Q

10

@artist Your implementation of Sieve is wrong. Read how to implement Sieve here under topic algorithm and variants : Sieve of Eratosthenes - Wikipedia . I have explained the complete logic of the problem in my answer. If you can implement it successfully, you will get AC.