Python比set for subtraction更节省内存

Question

我正在尝试编写一个函数，通过使用Sieve of Eratosthenes可以找到某个非常大的数下面的所有素数。我编写了函数：

def primes(limit):
    #efficient method for finding large primes
    l=set()
    i=1
    while i<limit+1:
        l.add(i)
        i+=2
    s=int(math.sqrt(limit))
    #recur until sqrt is small
    if s<=1000:
        ps=smallprimes(s)
    else:
        ps=primes(s)

    for p in ps:
        l-=set(multiples(p,limit+1)[1:])
    return [2]+(list(l)[1:])

其中smallprimes仅通过检查因子的数目来计算低于极限的素数，而multiples则计算低于极限的数的所有倍数。你知道吗

通过将非常大的限制传递给primes，我创建了大集合来“删除limits平方根以下所有素数的倍数”。你知道吗

有没有比使用集合更有效的方法从序列中“删除”数字？我想知道，因为我真的只需要减去两个数组，我不需要防止重复，等等

Answer 1

对于大型数据集，使用集合会有问题，因为哈希冲突的数量会显著增加，除此之外，还会产生不必要的存储开销。你知道吗

另一种解决方案是使用numpy掩码数组。数组中的索引是数字，该值指示它是否为素数。您可以通过使数字为2 * index + 1来进一步优化，以便只存储奇数。你知道吗

这只是一个例子。在大筛子上使用成套设备效率很低。你知道吗