与素数数量成比例的素数筛的空间复杂度是多少？

Question

我正在练习编写优化空间或时间复杂度的算法。以素数筛选法为例，最基本的要求是你必须存储找到的所有素数的列表。看起来，存储的空间至少要和找到的素数数量成正比，这样的算法才能达到最小的空间使用。

• 这样的想法合理吗？
• 这个算法的空间复杂度应该怎么评估呢？

维基百科关于阿特金筛的介绍 - 我不太明白的是，为什么一个筛选法可以使用 O(n^1/2) 的空间，而找到的素数数量却超过了这个值。这让我觉得，至少空间的使用量应该和素数的数量成正比。我是不是把可计数的数字和空间复杂度搞混了？

在这篇关于阿特金筛的论文中，他们的算法打印“直到 N 的素数……这里的‘内存’不包括打印机使用的纸张。”这似乎对空间的计算不太公平。

• 我希望能澄清一下，这个空间应该怎么测量/实际上是如何客观测量的。

def prime_sieve(limit):
    factors = dict()
    primes = []
    factors[4] = (2)
    primes.append(2)
    for n in range(3, limit + 1):
        if n not in factors:
            factors[n * 2] = (n)
            primes.append(n)
        else:
            prime = factors.get(n)
            m = n + prime
            while m in factors:
                m += prime
            factors[m] = (prime)
            del factors[n]
    return primes

Answer 1

空间复杂度的测量是非常公平的。如果你把 primes.append(n) 替换成 yield n，然后在一个消费者程序中逐个处理这些质数，而不是把它们全部存储起来，比如说为了找到一个具有特定属性的质数，那么所需的存储空间实际上是 O(1)，也就是和质数的数量无关。

(yield 是 Python 中用来创建 生成器 的一种方式，生成器是一种特殊的协程，它可以向调用者输出值，并保存函数的状态，以便可以再次进入这个函数。)

Answer 2

“使用素数筛选法时，至少你必须存储所有找到的素数列表。”

这说法不对。你只需要存储小于或等于你设定的最大值的平方根的素数，这样就能筛选出那个范围内的素数。

如果你的筛选方法是增量的、没有上限的，那么你只需要存储当前计算点的平方根以下（包括平方根）的素数。

这怎么可能呢？可以通过使用一个单独的素数来源来获取“核心”素数（也就是那些小于平方根的素数），这完全可以用同一个函数来计算——递归地进行。想了解更多，可以看看这个回答。

而且，不计算生成的素数也是完全可以的——你可以把它们发送到打印机，或者保存到外部文件等等。因此，这种筛选法的空间复杂度将是O( sqrt(N)/log(N) ) ~ O( sqrt( n/log(n) ))，其中n是小于N ~= n * log n的素数数量。

另外，不要去碰阿特金筛选法。听说它根本无法超越经过适当轮式优化的埃拉托斯特尼筛选法（可以搜索一下关于这个话题的GordonBGood的回答，比如这个）。

Answer 3

这个算法的空间复杂度是 len(numbers) + len(primes)，也就是列表的大小加上字典的大小。

在这种情况下，这个算法的表现比你想象中的要差，尤其是对于一个简单的质数筛选算法（limit）。因为 len(numbers) + len(primes) > limit，举个例子，当你调用 prime_sieve(100) 时，numbers 里会存储一些不相关的数字：

{129: 43, 134: 67, 141: 47, 142: 71, 146: 73, 158: 79, 166: 83, 178: 89, 194: 97, 102: 17, 104: 2, 105: 3, 106: 53, 110: 11, 111: 37, 112: 7, 114: 19, 115: 23, 116: 29, 117: 13, 118: 59, 120: 5, 122: 61, 123: 41, 124: 31}

有几种不同的质数筛选算法，它们的时间和空间复杂度各不相同；你可以参考一下 维基百科 和一些问题，比如 如何减少埃拉托斯特尼筛法在生成区间 a 到 b 之间的质数时的空间复杂度？

另外，注意到其实不需要用 prime = numbers.get(n)，因为你已经检查过 if n not in numbers，所以可以直接用 prime = numbers[n]。