You are not logged in. Please login at www.codechef.com to post your questions!

×

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

http://www.spoj.com/problems/PRIME1/

Plz help !!

asked 03 Dec '14, 22:23

chaman_amit's gravatar image

1★chaman_amit
871413
accept rate: 0%

edited 04 Dec '14, 14:39

betlista's gravatar image

3★betlista ♦♦
16.9k49115225

1

Try this case 1 999900000 1000000000

(03 Dec '14, 22:38) gautam943★

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

(04 Dec '14, 12:47) chaman_amit1★
1

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.

(04 Dec '14, 14:31) gautam943★

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 on my blog, and try to code it. Here are some more good articles on Segmented sieve

Hope it helps!

link

answered 04 Dec '14, 06:47

vicky002's gravatar image

1★vicky002 ♦♦
2561314
accept rate: 27%

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

link

answered 03 Dec '14, 22:36

ansh1star033's gravatar image

3★ansh1star033
206129
accept rate: 9%

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

link

answered 04 Dec '14, 11:13

chaman_amit's gravatar image

1★chaman_amit
871413
accept rate: 0%

1

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

(04 Dec '14, 14:24) gautam943★

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

(04 Dec '14, 14:49) betlista ♦♦3★
1

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

(04 Dec '14, 14:51) gautam943★

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

(05 Dec '14, 21:58) chaman_amit1★

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

(05 Dec '14, 22:01) chaman_amit1★

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

link

answered 04 Dec '14, 14:38

ansh1star033's gravatar image

3★ansh1star033
206129
accept rate: 9%

1

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

(04 Dec '14, 14:42) betlista ♦♦3★
1

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.

(04 Dec '14, 14:43) gautam943★
2

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

(04 Dec '14, 14:53) betlista ♦♦3★

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

(06 Dec '14, 00:00) ansh1star0333★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,738
×96
×74
×40
×7
×7

question asked: 03 Dec '14, 22:23

question was seen: 1,105 times

last updated: 06 Dec '14, 00:00