silendeath
Sep '21

My Code uses 2049M of memory (as per SPOJ) and get the error 'Runtime Error (SIGKILL), I know that the error is due to my code consuming more memory than allowed by SPOJ, but after searching online I am not able to fix it.

Please, look at my code and guide me.

def sieve(arr,a,b):
    arr[0] = 0
    arr[1] = 0
    for i in range(2,int(b+1/2)): #Instead of checking till n, we can check till n/2 <Read Why?>
        if arr[i] == 1: #If a number is prime, then it's multiples will be non prime.
            for i in range(i ** 2,int(b+1), i):
                arr[i] = 0 #Setting multiples of prime number to non-prime.
    for i in range(a,int(b+1)):
        if arr[i] == 1:
            print(i)

t = int(input())
while t > 0:
    t = t - 1
    a,b = input().split(' ')
    a = int(a)
    b = int(b)
    global arr
    arr =  [1]*int(b+1)
    sieve(arr,a,b)

Thank You.

  • created

    Sep '21

  • last reply

    Sep '21
  • 1

    reply

  • 581

    views

  • 2

    users

  • 2

    links

simes
Sep '21

Did you notice the upper limit for n? 10^9. Even if you could allocate an array that big, the sieve would take forever to run. (And why re-sieve for each test case anyway? The primes aren’t going to be any different.)

So yes, I expect you’re right, and the sigkill is because you trying to allocate an array with a billion elements.

But other causes of runtime errors could be a slightly malformed test case, for example, one with two spaces between the integers, or with a leading or trailing space.

Search this forum7 - there are plenty of posts about PRIME12.