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