Runtime error in SPOJ

Question

I just started with competitive programming. I am kinda stuck with this prime no. generator problem on SPOJ. Code works fine on GeeksforGeeks IDE but on SPOJ it gives a runtime error. The question goes like this:

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

Input: The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output: For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

Example

Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

and my solution is this:

# include<iostream>
# include <math.h>

using namespace std;

int main() {

int t;
cin>>t;
while(t--){
    int up,low;
    cin>>low>>up;
    int len = 1000000;
    bool arr[len];
    arr[1]=arr[0]=false;
    for(int i=2;i<=up;i++)
        arr[i]=true;

    for(int i=2;i<sqrt(up);i++) {
        if(arr[i]==true){
            for(int j=(i*i);j<=up;j+=i){
                arr[j]=false;
            }
        }
    }

    for(int i=low;i<=up;i++)
    {
        if(arr[i]==true)
            cout<<i<<endl;
    }
    if(t==1)
        cout<<endl;
}
return 0;

}

I have used Sieve of Eratosthenes to solve this problem.

Well `bool arr[len];` is not legal C++, that might be your problem. `bool arr[1000000];` would be OK. — john, Jul 16 '18 at 15:18
You should describe the error you are getting in more detail. "it gives a runtime error" is a little vague ;-) — sebrockm, Jul 16 '18 at 15:32
`bool arr[1000000];` could be a Stack Overflow.. Better use a `std::vector` — drescherjm, Jul 16 '18 at 15:54
You could define `len` as `const int` or `constexpr`, which would be better. However, the array is huge for the stack. You should declare it as `static` or move it outside `main`. — Thomas Matthews, Jul 16 '18 at 16:45
See https://stackoverflow.com/q/1887097/9254539. Your code only compiles because of a GCC non-standard extension, and allocating a large array on the stack like this could cause a stack overflow. — eesiraed, Jul 16 '18 at 17:09
Thanks a lot guys for your response! A great first experience at stack overflow :) now coming back to the problem ;) I tried all of your suggested approaches but the SPOJ compiler still gives a run time error (SIGSEGV @sebrockm ;-)) . — blackhoodcoder, Jul 21 '18 at 09:53
The suggestion given by @ThomasMatthews worked well for all the test cases which i gave on https://ideone.com/ . But again it gave a SIGSEGV on SPOJ. — blackhoodcoder, Jul 21 '18 at 09:55
Sometimes, a SIGSEGV on SPOJ means that you need to use a different algorithm. — Thomas Matthews, Jul 21 '18 at 16:26

score 1 · Answer 1 · answered Jul 21 '18 at 13:02

The SIGSEGV is well known in C++. It means that you are trying to access memory that you are not allowed to access. In your particular case it is very likely* that you try to access arr with a wrong index.

As you initialized it as bool arr[100000]; writing code like arr[i] is only valid for 0 <= i <= 99999. Now look at your for loops, e.g. the first one

for(int i=2;i<=up;i++)
    arr[i]=true;

Whenever you enter a number for up that is greater than 99999, you are causing undefined behavior here (most likely a SIGSEGV).

So you have to redesign your algorithm to store your boolean values, indicating if a number is prime, somehow differently.

* Note: I cannot be entirely sure if this is your issue because you didn't say for what input values of up and low this error occurs. When asking a question you should give as many infos as possible that allow to reproduce your issue.

Runtime error in SPOJ

1 Answers1