CODEWITHSUNDEEP
pythonpython-3.xruntime-errorprimes
user2694307
user2694307

Reputation: 383

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

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")

Upvotes: 1

Views: 369

Answers (2)

ceremcem
ceremcem

Reputation: 4360

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.

Upvotes: 0

abarnert
abarnert

Reputation: 365845

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.

Upvotes: 1

Related Questions