Python 素数代码在 spoj 上给出运行时错误(NZEC)

Question

我正在尝试为这个问题获得可接受的答案:http://www.spoj.com/problems/PRIME1/这不是什么新鲜事，只是希望在两个给定数字之间生成素数。最终，我编写了以下代码。但是 spoj 给了我运行时错误(nzec)，我不知道应该如何处理它。我希望你能帮助我。提前致谢。

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

Answer 1

查看问题定义:

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.

查看您的代码:

mySieve= [True] * (n+1)

因此，如果 n 为 1000000000，您将尝试创建一个包含 1000000001 个 bool 值的列表。这意味着您要求 Python 为十亿个指针分配存储空间。在 64 位平台上，这是 8GB——对于 Python 来说这很好，但很可能会让你的系统陷入交换 hell ，或者被限制或看门狗杀死。在 32 位平台上，这是 4GB，这将保证您出现 MemoryError。

该问题还明确包含此警告:

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

因此，如果您想以这种方式实现它，您将必须提供更紧凑的存储。例如，array.array('B', [True]) * (n+1)只需要 1GB，而不是 4 或 8。如果您以位而不是字节的形式存储它，您可以使其变得更小(128MB)，但这对代码的更改并不是那么简单。