Python prime number code giving runtime error(NZEC) on spoj

Question

I am trying to get an accepted answer for this question:http://www.spoj.com/problems/PRIME1/ It's nothing new, just wanting prime numbers to be generated between two given numbers. Eventually, I have coded the following. But spoj is giving me runtime-error(nzec), and I have no idea how it should be dealt with. I hope you can help me with it. Thanks in advance.

def is_prime(m,n):
    myList= []
    mySieve= [True] * (n+1)
    for i in range(2,n+1):
        if mySieve[i]:
            myList.append(i)
            for x in range(i*i,n+1,i):
                mySieve[x]= False
    for a in [y for y in myList if y>=m]:
        print(a)



t= input()
count = 0
while count <int(t):
    m, n = input().split()
    count +=1
    is_prime(int(m),int(n))
    if count == int(t):
        break
    print("\n")

@undefinedisnotafunction I am sorry I didn't mention that. It's Python 3. — user2694307, Jul 29 '14 at 20:49
If this is some output from an online test program, my first guess would be that your program either takes too long to run, so the tester aborts your program and says you've failed, or prints the wrong results, or doesn't follow the instructions in some other way. — abarnert, Jul 29 '14 at 20:55
Does the documentation on the test site says that "NZEC" means? — abarnert, Jul 29 '14 at 20:58
One last thing: It looks like that site has a forum specifically designed for people to ask questions like this. So… why not ask on that forum, where everyone knows about the site, instead of here? — abarnert, Jul 29 '14 at 20:59
@abarnert NZEC means non-zero exit code according to SPOJ. I know they have a forum but I have come here first as I thought I could get answers faster than there. — user2694307, Jul 29 '14 at 21:01
You should be using a segmented Sieve of Eratosthenes as in [http://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes/10249801#10249801](http://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes/10249801#10249801). — user448810, Jul 29 '14 at 21:13
@abarnert NZEC means Non zero exit code (Code must return 0 on succesfull completion) — Ashwani, Oct 10 '14 at 09:50
@AshwaniDausodia: The OP already answered that 4 months ago. — abarnert, Oct 10 '14 at 17:26
@abarnert oh i didn't see that also didn't realize that it was asked 4 months ago — Ashwani, Oct 10 '14 at 19:01

abarnert · Accepted Answer · 2014-07-29T21:09:26.997

1

Looking at the problem definition:

In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Looking at your code:

mySieve= [True] * (n+1)

So, if n is 1000000000, you're going to try to create a list of 1000000001 boolean values. That means you're asking Python to allocate storage for a billion pointers. On a 64-bit platform, that's 8GB—which is fine as far as Python's concerned, but might well throw your system into swap hell or get it killed by a limit or watchdog. On a 32-bit platform, that's 4GB—which will guarantee you a MemoryError.

The problem also explicitly has this warning:

Warning: large Input/Output data, be careful with certain languages

So, if you want to implement it this way, you're going to have to come up with a more compact storage. For example, array.array('B', [True]) * (n+1) will only take 1GB instead of 4 or 8. And you can make it even smaller (128MB) if you store it in bits instead of bytes, but that's not quite as trivial a change to code.

edited Jul 29 '14 at 21:09

answered Jul 29 '14 at 21:03

abarnert

354,177
51
601
671

I am very new to python, and this piece of code was the only implementation of "sieve of eratosthenes" that I could code. But as your guide, I will try to do it in the way you've mentioned although I don't have any idea how to. Thanks for the fast answer, I'd better read some more about this. – user2694307 Jul 29 '14 at 21:16
@user2694307: I'm not suggesting any change to your sieve code. That _might_ turn out to be wrong, or too slow, or whatever, but until you can actually get past this problem, you won't find that out. All you have to do is change the `[True] * (n-1)` to something more compact, like the `array.array` expression I showed, and your code should just work with 1/8th the memory, which will either solve your problem or let you find the next one. – abarnert Jul 29 '14 at 21:30
@user2694307: Also, I notice that the winning answer uses 256MB of memory, which implies that they aren't demanding that you use segmenting or any other more complicated technique to avoid linear memory usage, just demanding that you keep it under some limit like 2GB. – abarnert Jul 29 '14 at 21:31

ceremcem · Answer 2 · 2014-07-29T21:21:27.440

0

Calculating prime numbers between two numbers is meaningless. You can only calculate prime numbers until a given number by using other primes you found before, then show only range you wanted.

Here is a python code and some calculated primes you can continue by using them:

bzr branch http://bzr.ceremcem.net/calc-primes

This code is somewhat trivial but is working correctly and tested well.

edited Jul 29 '14 at 21:21

answered Jul 29 '14 at 21:14

ceremcem

3,900
4
28
66

Python prime number code giving runtime error(NZEC) on spoj

2 Answers2