Nov 2014
9 / 9
Nov 2014
Nov 2014
zux
Nov '14

Hi. can anyone point me into any directions why is this code getting runtime error NZEC?
Semms to run very ok on my machine, tried a lot of test cases and no problems.
This is my second problem, so i probably have a newbie problem.

#generate prime numbers
def primes(max):
    primes = dict()
    for i in range(2, max+1): primes[i] = True
    for i in primes:
        for f in range(i, max+1, i)[1:]:
            primes[f] = False
    return [i for i in primes if primes[i]==True]
count = int(raw_input())
list1 = []
list2 = []
if count <= 10:
    for y in range(count):
        raw=raw_input()
        split1 = raw.split(" ")
        list1.append(int(split1[0]))
        list2.append(int(split1[1]))
    print 

min = min(list1)
max = max(list2)

result = primes(max)

for i in range(count):
    for c in range(len(result)):
        if result[c] >= list1[i] and result[c] <= list2[i]:
            print result[c]

    print
numerix
Nov '14

There were "no problems" because you checked with weak testcases.
According to the problem description the upper limit can be up to 1000000000.
Try it.

zux
Nov '14

well i tried this:

5
100 200
10000 10100
100000 100100
1000000 1000100
10000000 10000100

and also:

1
9000000 9010000

2
9900000 10000000
300 10000

it was not fast, but there was a result and no runtime errors.

i've considered building the list starting from the smallest first number or even building a new list for every test case, but that would only be usefull in certain test cases, right? Like my last one, would be faster if the list was created starting from first number, but the first case would perform better if there was a smaller list for every case.
Anyway, no idea why it works on my pc and not on the judge. Any more test cases i can run?

Another idea i have is to optimize the output search, but is there a way to find the index of a certain list member? On the other hand, that won't work if the first and last numbers are not prime, then i'd have to search for the closest prime that is in the list

numerix
Nov '14

As I told you: weak test cases! Check the worst case and you know the reason for the NZEC.

zux
Nov '14

Ok, I'm stuck here.
Can it get worse than this?

5
10 100010
100 100100
1000 101000
10000 110000
9900000 10000000

The list generation takes very long and the output even more, but still no errors. Or am I missing something?
timeout would be perfectly reasonable

numerix
Nov '14

Why to you think your testcases are strong? You still did not check the worst case. Without looking at the problem's constraints, you won't find out.
Exact reading is the first (and necessary) step towards problem solving.

zux
Nov '14

oh, there is another zero...
now i get it.
so the correct approach would be to use two algorithms depending on the input numbers?

numerix
Nov '14

No, a good approach would be to think about how to calculate all primes between 10⁹-10⁵ and 10⁹ efficiently.
I you managed to do so, it shouldn't be a problem to handle all other (weaker) intervalls with the same algorithm.

zux
Nov '14

thanks, looks like i got it working, seems very simple now. and it runs very fast.
but now i get wrong answer frowning

this probably needs some more optimizations

#generate prime numbers
import math
def primes_small(max):
    primes = dict()
    primes[2] = True
    for i in xrange(3, max+1): primes[i] = True
    for i in primes:
        for f in range(i, max+1, i)[1:]:
            primes[f] = False
    return [i for i in primes if primes[i]==True]
def primes_big(min, max, primes_small):
    primes_big = dict()
    for i in range(min, max+1): primes_big[i] = True
    for i in primes_small:
        for f in range(int(min-(min%i)), max+1, i):
            if f >= min and f <= max:
                primes_big[f] = False
    if min <= 3:
        primes_big[1] = False
        primes_big[2] = True
        primes_big[3] = True
    return [i for i in primes_big if primes_big[i] == True]
count = int(raw_input())
list1 = []
list2 = []
if count <= 10:
    for y in range(count):
        raw=raw_input()
        split1 = raw.split(" ")
        list1.append(int(split1[0]))
        list2.append(int(split1[1]))
    min = min(list1)
max = max(list2)
result_small = primes_small(int(math.sqrt(max))+1)
for i in range(count):
    result_big = primes_big(list1[i], list2[i], result_small)
    for c in range(len(result_big)):
        print result_big[c]
    print