python - 数据与素数成正比的素数筛的空间复杂度是多少？

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

这个算法的空间复杂度是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，因此您可以使用素数 = 数字[n]。