Segmented sieve(Sigfpe)

[1vf9z8AR]

Finally understood segmented sieve and made it work. But on spoj I am getting sigfpe. I can't figure out why this is happening.

Question link:
https://www.spoj.com/problems/PRIME1/

  #include<iostream>
#include<math.h>
using namespace std;
int main()
{
    long int low,high,t,i,j,mult;
    cin>>t;
    while(t>0)
    {
    cin>>low>>high;
    long int upper1=sqrt(high);
    long int upper2=sqrt(upper1);
    long int prime[upper1],storeprime[upper1],pos=0;
    prime[0]=0;
    prime[1]=0;
    for(i=2;i<upper1;i++)   //prime[] is to find primes
        prime[i]=1;
    for(i=2;i<upper1;i++)  //sieve to find primes till sqrt(high)
    {
        if(prime[i]==1)
        {
            storeprime[pos++]=i;    //storeprime[] is to store primes
            for(mult=2;i*mult<=upper1;mult++)
            {
                prime[i*mult]=0;
            }
        }
    }
  long int range[high-low];   //to find primes in given range
    for(i=0;i<high-low;i++)
    {
        range[i]=1;
    }
    for(i=0;storeprime[i]<=high/storeprime[i];i++) //segmented sieve
    {
       long int start=low/storeprime[i];
        start*=storeprime[i];
        for(j=start;j<=high;j+=storeprime[i])
        {
            if(j!=storeprime[i])
                range[j-low]=0;
        }
    }
    for(i=0;i<high-low;i++)     //to print all primes in given range
    {
        if(range[i]==1)
            if(i+low!=0 && i+low!=1)
                cout<<i+low<<endl;
    }
    t--;
    }
}

[Thomas1965]

Test it on your PC with huge numbers. It's possible that you get a stack overflow.

[Thomas1965]

Another possible problem is that on line 34, 36 high/storeprime[i] lead to division by zero.

[1vf9z8AR]

@Thomas1965
but how I do I make it work for big numbers? I used long int and in the question, it is given that high-low<=10^5.

Also, I am not able to find why storeprime[] would contain zero.

[Thomas1965]

It seems do don't fully understand how these sieves work.
You need to store boolean values not numbers.
I think you better start with a simple sieve and use a vector<bool>. In this way you can easily store millions of bools. I know that it is common practice on codechef and similar sites to use these VLA but it's really bad practice to use these illegal constructs.

Try do do this:

#include<iostream>
#include<vector>

using namespace std;

int main()
{
  size_t count;
  cin >> count;
  
  vector<bool> primes(count, true);
  primes[0] = primes[1] = false;

  // TO DO - mark all non primes as false

  // print all primes here

}

[1vf9z8AR]

After using bool nothing is coming in output :(

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
int main()
{
    long int low,high,t,i,j,mult;
    cin>>t;
    while(t>0)
    {
    cin>>low>>high;
    long int upper1=sqrt(high);
    long int upper2=sqrt(upper1);
    long int storeprime[upper1],pos=0;
    vector<bool>prime(upper1,true);
    prime[0]=false;
    prime[1]=false;
    for(i=2;i<=upper1;i++)
    {
        if(prime[i]==true)
        {
            storeprime[pos++]=i;
            for(mult=2;i*mult<=upper1;mult++)
            {
                prime[i*mult]=false;
            }
        }
    }
  vector<bool>range(high-low,true);
    for(i=0;storeprime[i]<=high/storeprime[i];i++)
    {
       long int start=low/storeprime[i];
        start*=storeprime[i];
        for(j=start;j<=high;j+=storeprime[i])
        {
            if(j!=storeprime[i])
                range[j-low]=false;
        }
    }
    for(i=0;i<high-low;i++)
    {
        if(range[i]==true)
            if(i+low!=0 && i+low!=1)
                cout<<i+low<<endl;
    }
    t--;
    }
}