相关疑难解决方法(0)

埃拉托斯特尼筛法内存约束问题

我目前正在尝试为 Kattis 问题实现埃拉托斯特尼筛的一个版本，但是，我遇到了一些内存限制，我的实现无法通过。

这是问题陈述的链接。简而言之，这个问题要求我首先返回小于或等于n 的素数数量，然后求解一定数量的查询，判断数字i是否为素数。内存使用量限制为 50 MB，并且只能使用 python 标准库（无 numpy 等）。内存限制是我陷入困境的地方。

到目前为止，这是我的代码：

import sys

def sieve_of_eratosthenes(xs, n):
    count = len(xs) + 1
    p = 3 # start at three
    index = 0
    while p*p < n:
        for i in range(index + p, len(xs), p):
            if xs[i]:
                xs[i] = 0
                count -= 1

        temp_index = index
        for i in range(index + 1, len(xs)):
            if xs[i]:
                p = xs[i]
                temp_index += 1
                break
            temp_index += 1 …