Getting frustrated

what wrong in this code!!
it works fine in codeblocks and ideone but when i submitted this solution on spoj then it will
raise exception i.e SIGSEGV … HOW can i sort out this issue plz help me

#include <cstdio>
#include <string.h>

#include <iostream>

using namespace std;

void markMultiples(bool arr[], int a, int n)
{
    int i = 2, num;
    while ( (num = i*a) <= n )
    {
        arr[ num-1 ] = 1; 
        ++i;
    }
}


void SieveOfEratosthenes(int a, int n)
{

    if(a<2){
    	a=2;
    }
    if (n >= 2)
    {
        
        bool arr[n];
        memset(arr, 0, sizeof(arr));

                for (int i=1; i<n; ++i)
        {
            if ( arr[i] == 0 )
            {
            
                if((i+1)>=a && (i+1)<=n)
                printf("%d\n", i+1);
                markMultiples(arr, i+1, n);
            }
        }
    }
}

int main()
{
int n;
cin>>n;
while(n--)
{
	int a,b;
	cin>>a>>b;
	SieveOfEratosthenes(a,b);
}


return 0;
}

Plz help !!

This requires implementation of segmented sieve!!,because here you have been given range in which you have to generate primes.One way is to find all the primes upto maximum limit,then eliminate primes upto minimum limit.But then that would also give you TLE. Do take a look at this :-
http://primesieve.org/segmented_sieve.html

Try this case 1 999900000 1000000000

1 Like

You can not solve this using Sieve only as time limit is so tight, You have to use Segmented Sieve technique!
Read About [Segmented sieve][1] on my blog, and try to code it.
Here are some more good articles on Segmented sieve

  • [segmented sieve of Eratosthenes][2]
  • [Segmented Sieve][3]

Hope it helps!
[1]: http://codereuler.quora.com/Segmented-Sieve-Of-Eratosthenes
[2]: http://sweet.ua.pt/tos/software/prime_sieve.html
[3]: http://www.thelowlyprogrammer.com/2012/08/primes-part-2-segmented-sieve.html

1 Like

My problem is that how it is given segmentation fault error i.e. SIGSEV

How to do this bz i think it exceeds the limit of long long range!!
plz help me!!

Read this http://www-ee.eng.hawaii.edu/~tep/EE160/Book/chap14/subsection2.1.1.8.html
Stack memory is smaller. Your program needs around 1gb memory. So use dynamic allocation (using malloc) or declare a global array(outside main function). This will remove the runtime error but will give TLE. Also read this http://gribblelab.org/CBootcamp/7_Memory_Stack_vs_Heap.html and this http://pages.cs.wisc.edu/~calvin/cs110/LOCAL_GLOBAL.html

1 Like

Range of int for Turbo C/C++ is -32768 to 32767 because it is a 16bit compiler. Range of various datatypes in 32bit compilers are given here http://msdn.microsoft.com/en-IN/library/s3f49ktz.aspx 1000000000 can easily fin in int.

1 Like

@gautam94
I too tried that,declaring the bool array globally in the above code.Still it gave Segfault.This can only be the reason,but i think the bool array which is passed as an argument,should also it’s size.Because,the end of array is not known.

Even if you allocate it globally, you need 1GB (iff sizeof(bool) is 1) of memory which is too much !

Read more here - http://discuss.codechef.com/questions/7589/why-do-i-get-a-sigsegv/7590

1 Like

Where did you try? I submitted that on SPOJ and got TLE. Dont know about the memory limit at IDEONE. It might be lower than 1GB. On SPOJ its 1536 MB so it works.

1 Like

Your root cause finding is correct, but your proposed solution is not, in CodeChef environment it is not possible to allocate 1GB on heap also…

@betlista Yes I checked that before posting this. However the OP is solving this problem on SPOJ where memory limit is 1500 MB.

1 Like

Sorry I missed it is SPOJ problem, it’s on codechef also - http://www.codechef.com/problems/PRIME1 sorry :wink:

2 Likes

Thanks gautam sir!! i change the bool to make it global variable now it is giving time limit exceeded!!

Now my program takes 956 mb and program max. limit is 1536 so memory is not a issue now!!

@gautam94
I tried it at IDEONE. That may be the reason.