<p>这的确是一个非常具有挑战性的问题。最大可能的<code>N</code>为10^8,假设没有任何开销,每个值使用一个字节将导致几乎100 MB的数据。即使只存储奇数而将数据减半,在考虑开销后,也会使您的数据接近50MB</p>
<p>这意味着解决方案必须使用以下几种策略中的一种或多种:</p>
<ol>
<li>为素性标志数组使用更有效的数据类型。Python列表维护指向每个列表项的指针数组(64位Python上每个指针有4个字节)。我们实际上需要原始二进制存储,这在标准python中几乎只剩下<code>bytearray</code></李>
<li>在筛选中每个值只使用一位,而不是整个字节(Bool技术上只需要一位,但通常使用完整字节)</李>
<li>细分以删除偶数,也可能是3、5、7等的倍数。</em></li>
<li>使用<a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve" rel="nofollow noreferrer">segmented sieve</a></li>
</ol>
<p>我最初试图通过在筛选中只存储每个值1位来解决这个问题,虽然内存使用率确实在要求范围内,但Python缓慢的位操作将执行时间推得太长。同时,很难找出复杂的索引以确保可靠地计算正确的位</p>
<p>然后,我使用bytearray实现了仅奇数的解决方案,虽然速度快了很多,但内存仍然是个问题</p>
<p>Bytearray奇数实现:</p>
<pre><code>class Sieve:
def __init__(self, n):
self.not_prime = bytearray(n+1)
self.not_prime[0] = self.not_prime[1] = 1
for i in range(2, int(n**.5)+1):
if self.not_prime[i] == 0:
self.not_prime[i*i::i] = [1]*len(self.not_prime[i*i::i])
self.n_prime = n + 1 - sum(self.not_prime)
def is_prime(self, n):
return int(not self.not_prime[n])
def main():
n, q = map(int, input().split())
s = Sieve(n)
print(s.n_prime)
for _ in range(q):
i = int(input())
print(s.is_prime(i))
if __name__ == "__main__":
main()
</code></pre>
<p>由此进一步减少内存,应能使其正常工作</p>
<p><strong>编辑:</strong>
此外,删除2和3的倍数似乎不足以减少内存,尽管<a href="https://zhuyifei1999.github.io/guppy3/" rel="nofollow noreferrer">^{<cd3>}</a>似乎表明我的使用量实际上略低于50MB。🤷♂️ </p>