python - 在哈希集中保留非素数与创建布尔数组之间的空间和时间复杂度有什么区别？

我得到一个整数 n，并告诉我返回从 1 到 n 的所有素数。

我知道这个问题已经在这里回答了很多次，但我的问题是关于跟踪 non-primes 的两种方法。这两种方法是：

创建一个array of size n，其中每个索引表示从 1 到 n 的数字，Boolean (i.e. True or False)如果不是素数，则用于标记每个条目；the array is initially empty，但是当我们遇到素数时，我们会将数组中所有素数的倍数标记为 False（即不是素数），这样当我们得到这个数字时，我们不需要“检查”它是否是素数。否则，我们将通过尝试从 0 到该数字的模数来“检查”该数字是否为素数。
创建 aset()并按照 1 从 0 迭代到 n。每次我们遇到一个素数时，存储它在这个集合中的所有倍数，对于从 0 到 n 的每个数字，我们首先检查它是否在这个集合中，然后再测试不管是不是素数。

以上两种方法在时间和空间复杂度方面有什么区别吗？

标签： pythontime-complexityprimesspace-complexity

TLDR：从大的角度来看，它们在时间和空间上都是等价的。然而，在实践中，存在着巨大的差异。

时间复杂度：我们正在处理所有数字，在两种情况下都设置所有倍数（N/2 + N/3 + N/5+ ...）。在这两种情况下，设置标志都需要 O(1) 时间。在这两种情况下，空间复杂度都是 O(n)。

不同的是，list 每个布尔值只占用几个字节。Set 也使用相同的几个字节来存储值，但还必须存储键哈希、维护冲突记录和处理大小调整。虽然这一切仍然归结为渐近 O(1) 复杂度，但它在实践中需要考虑一个相当大的常数乘数。