"质数筛选算法的空间复杂度与质数数量成比例时是多少？"

Question

我在练习时空优化算法。对于初级筛子，至少你必须存储一份找到的所有质料的清单。似乎与质数成比例的数据是这种算法所能使用的最小空间量。在

• 这个理由有效吗？在
• 如何评估该算法的空间复杂度？在

From Wikipedia about the sieve of Atkin-我不确定的是当质数超过这个数时，筛子如何使用O（n^1/2）空间。这就是为什么空间至少必须与素数成正比的原因。我是不是把可数数和空间复杂性搞混了？在

In this paper on the sieve of Atkin，他们的算法打印“直到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

" With prime sieves, at minimum you must store a list of all primes found. "

不正确。你只需要低于（包括）上限平方根的素数，就可以筛选出这个范围内的素数。在

如果你的筛选是递增的，无界的，那么你只需要有低于（包括）当前生产点平方根的素数。在

怎么可能？通过使用一个独立的素数为“核心”素数（低于sqrt的那些素数），这完全可以用相同的函数递归地计算。有关示例，请参见this answer。在

不计算产生的素数是完全合法的-你可以将它们发送到打印机或外部文件等。因此，对于小于em>n素数的n~=n*logn，这样一个筛选的空间复杂度将是O( sqrt(N)/log(N) ) ~ O( sqrt( n/log(n) ))。在

另外，不要靠近阿特金的筛子。街上的说法是，用它不可能击败埃拉托什尼的筛子（通过GordonBGood搜索答案，比如this one）。在

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}

有几个素数筛，具有不同的时间和空间复杂性；参见例如Wikipedia和类似How do i reduce the space complexity in Sieve of Eratosthenes to generate prime between a and b?的问题

另外，请注意，不需要prime = numbers.get(n)-您已经选中了if n not in numbers，所以您可以使用prime = numbers[n]。在