Sigsegv Error in finding prime in a range

Question

While solving a question to find prime in a given range ,I am getting a Sigsegv error and I am unable to find where is my mistake and How to correct it

#include<iostream>
#include<cmath>
using namespace std;
int primes[10000000];// stores prime upto a max value
int prime[10000000];//stores prime in a given range
int main()
{
  long long int t,m,n,s,k,q;
  for(long long int i=1;i<=1000000;i++){
      primes[i]=1;
      primes[1]=0;
  }

    //stores prime using sieve    
    for(long long int i=2;i<=sqrt(1000000);i++) 
    {
        if(primes[i]==1)
        {
            for(long long int j=2;i*j<=1000000;j++)
            {
                primes[i*j]=0;
            }
        }   
    }
    cin>>t;
    while(t--)
    {
        cin>>m>>n;
        //marking all indices as 1 
        for(long long int i=m;i<=n;i++)      
        {
          prime[i]=1;
        }
        //calculating which offset to mark
        for(long long int i=2;i<=n-m+1;i++)       
        {
            if(primes[i]==1)
            {
                long long int x=(m/i)*i;
                while(x<m)
                x=x+i;   
                for(long long int j=x;j<=n;j=j+i)
                {
                    if(primes[j]==0)
                    prime[j]=0;
               }  
             }
           }         
        for(long long int i=m;i<=n;i++)
        {
            if(prime[i]==1&&i!=1)
            cout<<i<<"\n";
        }
    }
    return 0;
}

In C++, indices go from 0 to size-1. You should at least update your for loops to respect this rule. — steiner, Apr 21 '16 at 14:05
possible duplicate http://stackoverflow.com/questions/7559236/dynamic-sieve-algorithms-for-prime-generation?rq=1 — Tejendra, Apr 21 '16 at 14:06
@fetherolfjd-Well on Spoj compiler they are just showing Runtime (sigsegv) error — Beginner, Apr 21 '16 at 14:10
There's so much wrong with this code beside the index overrun that the only viable answer would be 'read at least a few of the hundreds of topics about PRIME1 here and at Code Review'. — DarthGizka, Apr 21 '16 at 14:12
@steiner-I am not getting you,in this way I am getting the answer on my compiler but not on SPOJ compiler — Beginner, Apr 21 '16 at 14:12
@DarthGizka-Thren why it is giving correct answer on small values — Beginner, Apr 21 '16 at 14:15
@Beginner you can not access the last element of your array with : prime[10000000] . You must use prime[9999999]. And the first element is prime[0], not prime[1] — steiner, Apr 21 '16 at 14:22
@steiner: the arrays are 10 times as big as the highest index used for accessing them. Count the zeroes... — DarthGizka, Apr 21 '16 at 14:24
The input variables `m` and `n` can receive values up to the PRIME1 limit of 10^9, and thus can exceed the limit of the statically allocated arrays (10^7) by a factor of up to 100. Instant crash. Inputs should never be used without adequate validation... — DarthGizka, Apr 21 '16 at 16:51

DarthGizka · Answer 1 · 2016-04-21T16:33:21.087

The compiler you are using may not allow the static allocation of big chunks of data like

int primes[10000000];

That's more than 2^25 bytes. Such a big chunk might exceed the capabilities of the compiler or its runtime on SPOJ. It might be possible to new or malloc() such a big chunk, but that workaround would probably lead you down a blind alley.

Another problem is that you are reading m and n from input without verifying that they are within safe limits. At least one of the test cases on SPOJ will be two orders of magnitude above the limits of your code because your allocation is 10^7 but the SPOJ limit is 10^9. This means that a crash is inevitable.

You do not need a full 32-bit integer for holding a boolean value; you could use bool and thus cut memory requirements to one fourth. Or you could treat each byte-sized array cell as a packed bitmap with 8 bits, cutting memory use to 1/32 compared to now. And since you are using C++, everything is already neatly packaged for you in the form of std::vector<bool> (which does bit packing under the hood).

Note: the arrays would have to be a hundred times as big for sieving all numbers up to the PRIME1 limit of 1,000,000,000. Although it is possible to sieve all the numbers in that range (the time limit is more than generous - about 10000 times what it needs to be for this task), it is probably not easy for someone who is completely new to programming.

However, the task does not ask for the sieving of a billion numbers. It only asks for the sieving of a small handful of ranges, each of which is no wider than 100001 numbers. Even simple, unoptimised code can do that in under a millisecond, even with std::vector<bool> which is an order of magnitude slower than any sensible data structure.

The keyword to look out for is 'windowed Sieve of Eratosthenes'. There are hundreds of topics here and over on Code Review that deal with PRIME1. Have a peek.

surajs1n · Accepted Answer · 2016-04-28T15:27:50.287

Consider a case:

1
100000000 100000009

When I ran your code on ideone link: here.

It gave Run-time Error.

Reason: You've initialized the prime array of the size 10⁷ but the range of m, n can reach upto 10⁹.

Therefore, once prime[i]=1 is encountered, your system crashes.

for(long long int i=m;i<=n;i++)      
{
      prime[i]=1;
}

Suggestion: Learn Sieve of Eratosthenes. And since the range of m, n can be
1 <= m <= n <= 1000000000, n-m<=100000

If we take the sqrt-root of the 10⁹ then it will come as near to 31622. So, that's why we picked up an array num of size 32000 (in my code). After that, we calculated the number of primes lying in the range of 2 - 32000.

Now, consider three cases:

When m and n both are less than 32000. Then simply use the calculated prime array and print the required prime numbers.
When both m and n are outside the range of 32000, then check whether a number i (in the range of m and n) is not divisible by the any prime number (present in prime array in the code). If the i is not divisible by any of the number then print it.
If the range of m and n is partially less than 32000 and partially outside the 32000. Then split the range into two parts, one which is completely less than and equal to 32000, and another which is completely greater than 32000. And repeat the Step-1 for the first range and Step-2 for the second range.

Below is my code, please find it useful but don't copy and paste it on SPOJ.

#include<stdio.h>
#include<math.h>

int num[32000] = {0},prime[3500],prime_index = -1;

int main() {
    prime[++prime_index] = 2;
    int i,j,k;

    for(i=3;    i<179;     i += 2) {
        if(num[i] == 0) {
            prime[++prime_index] = i;

            for(j = i*i, k = 2*i;    j<=32000;   j += k) {
                num[j] = 1;
            }
        }
    }

    for(;   i<=32000;   i+= 2) {
        if(num[i] == 0) {
            prime[++prime_index] = i;
        }
    }

    int t,m,n;
    scanf("%i",&t);
    while(t--) {
        scanf("%i%i",&m,&n);

        if(m == 1)
            m++;

        if(m == 2 && m <= n) {
            printf("2\n");
        }

        int sqt = sqrt(n) + 1, arr[100005] = {0};

        for(i=0;    i<=prime_index; i++) {
            if(prime[i] > sqt) {
                sqt = i;
                break;
            }
        }

        for(;   m<=n && m <= prime[prime_index];   m++) {
            if(m&1 && num[m] == 0) {
                printf("%i\n",m);
            }
        }

        for(i=0;    i<=sqt;     i++) {
            j = prime[i] * (m / prime[i]);

            if(j < m) {
                j += prime[i];
            }

            for(k=j;    k<=n;   k += prime[i]) {
                arr[k-m] = 1;
            }
        }

        for(i=0;    i<=n-m; i++) {
            if(!arr[i]) {
                printf("%i\n",m+i);
            }
        }

        printf("\n");
    }
    return 0;
}

Any doubt comments most welcome.

The *segmented* sieve doesn't really help here (it does the same work as the unsegmented sieve, only in portions that do not exceed the L1 cache size). The point is to sieve only the *windows* required by the task, using a *windowed* sieve that may be segmented or not. That way only a few hundred thousand numbers need to be sieved instead of a billion. And the rest of your answer repeats only what was already written by others a week ago. Hence -1. — DarthGizka, Apr 28 '16 at 13:11
To complete the sieve nomenclature: an *iterated* sieve does the same work as a plain sieve but reuses a smaller sieve over and over (preferrably L1 cache size) instead of allocating a huge chunk that represents all numbers to be sieved. A [*rolling* or *sliding* sieve](http://stackoverflow.com/a/36725003/4156577) is similar but much simpler in structure and most suited for lazy generators or situations where performance doesn't matter (one or two orders of magnitude slower than optimised sieves). Iterated and segmented sieves are often conflated, because they're both focussed on the L1 cache. — DarthGizka, Apr 28 '16 at 13:18
@DarthGizka. Please check my edit, and let me know if any point is still missing. I accidentally added the point **Segmented Sieve**, because i mistook this **PRIME1** with another question on **SPOJ**. I had already solved this question long time, i guess 4 years ago. — surajs1n, Apr 28 '16 at 15:45
I've withdrawn the -1 because now your answers adds something that is new; however, your code does not quite deserve a +1 yet... The approach - a windowed sieve - is indeed an excellent choice for this task but I doubt whether anyone *who does not know the algorithm yet* can learn from your code how it works; nor is it a good example for others to follow. You might want to post it on Code Review, for advice on how to make it much slimmer, more efficient and - most importantly - more robust and more self-documenting/self-explanatory. And you can apply it all to PRIME1's big bad brother, PRINT. — DarthGizka, Apr 28 '16 at 16:15
Here's the link for [PRINT](http://www.spoj.com/problems/PRINT/) (it didn't fit into the previous comment); there are other prime sieving tasks on SPOJ that are even more challenging, like [TDKPRIME](http://www.spoj.com/problems/TDKPRIME/) or [TDPRIMES](http://www.spoj.com/problems/TDPRIMES/) for example. — DarthGizka, Apr 28 '16 at 16:19
@DarthGizka. Thanks for your prompt reply friend and thanks for your suggestion, I will keep that in my mind next time. I have already solved all of these questions you just mentioned. — surajs1n, Apr 28 '16 at 16:49

Sigsegv Error in finding prime in a range

2 Answers2