擅长:python、mysql、java
<p>这个算法的空间复杂度是<code>len(numbers) + len(primes)</code>;列表的大小加上字典的大小。在</p>
<p>在本例中,该算法的<em>比您预期的朴素筛(<code>limit</code>)更糟糕。<code>len(numbers) + len(primes) > limit</code>因为例如对于<code>prime_sieve(100)</code>,以下不相关的数字存储在<code>numbers</code>中:</p>
<pre><code>{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}
</code></pre>
<p>有几个素数筛,具有不同的时间和空间复杂性;参见例如<a href="http://en.wikipedia.org/wiki/Generating_primes#Complexity" rel="nofollow noreferrer">Wikipedia</a>和类似<a href="https://stackoverflow.com/q/12430495/3001761">How do i reduce the space complexity in Sieve of Eratosthenes to generate prime between a and b?</a>的问题</p>
<p>另外,请注意,不需要<code>prime = numbers.get(n)</code>-您已经选中了<code>if n not in numbers</code>,所以您可以使用<code>prime = numbers[n]</code>。在</p>