Jun 2009
1 / 4
Jun 2009
Jun 2009
k4rt33k
Jun '09

Hello Everyone,
I am new to python.I am trying to solve PRIME 1 problem using sieve of Eratosthenes.But I am getting NZEC run time error.My submission id is 2478137.I am also submitting the code here

test_cases = int(raw_input(""))
count = 0
while(count < test_cases):
    input = raw_input("")
    input = input.split()
    lowlimit = int(input[0])
    highlimit = int(input[1])
    primelist = range(2,highlimit+1)
    limit = highlimit//2+1
    number = 2
    while(number < limit):
        if(primelist[number-2]):
            primelist[2*(number-1)::number] = [0]*(highlimit//number-1)
        number = number+1
    primelist = filter(None,primelist)
    if(lowlimit!=1):
        primelist = primelist[lowlimit-2:]
    for prime in primelist:
        print prime
    if(count!=test_cases-1):
        print ""
    count = count + 1

What am I currently doing wrong and any pointers in the right direction?

Cheers
Karteek

  • created

    Jun '09

  • last reply

    Jun '09
  • 3

    replies

  • 201

    views

  • 2

    users

numerix
Jun '09

I'm not sure what causes the error, but you could improve the input and make it somewhat more pythonic:

testcases = int(raw_input())
for t in xrange(testcases):
    low, high = map(int, raw_input())

It is better to use functions, e.g. use a function main() that handles the input and call a function primes(low, high) that
calculates a list of primes and returns that list to main().

Then you should run some tests with function primes(), e.g. low = 9 and high = 13 ... smiley

k4rt33k
Jun '09

Hey Numerix,
Thanks for the reply.My guess is that the stack is overflowing.So I am following a double sieve approach to reduce the size of the list that I store.

Thanks for the tip.But same error again. frowning

numerix
Jun '09

No, it isn't a stack problem, as there are no stack-operations (e.g. recurrence).

Before posting your code, check it locally with
- boundary cases, e.g. "1 1"
- worst case, i.e. "999900000 1000000000" (time limit! SPOJ machines are slow!)
- some random stuff (e.g. "9 13" for which your code produces the wrong result as I posted before)

If it has passed all these tests, then - maybe smiley - it will get AC.

P.S. Work on it, don't give up. For me, PRIME1 was the first problemset at SPOJ. I spent days on it and until now my solution is the fastest pure python solution (i.e. without psyco).

Suggested Topics

Want to read more? Browse other topics in Python or view latest topics.