Getting frustrated

help
issue
out
sort
to

#1

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* == 0 )
            {
            
                if((i+1)>=a && (i+1)<=n)
                printf("%d

", 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 !!


#2

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


#3

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


#4

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


#5

@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.


#6

Try this case 1 999900000 1000000000


#7

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


#8

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


#9

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.


#10

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


#11

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.


#12

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…


#13

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


#14

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


#15

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


#16

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


#17

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