<p>我认为您可以尝试使用布尔值列表来标记其索引是否为素数:</p>
<pre class="lang-py prettyprint-override"><code>def sieve_of_erato(range_max):
primes_count = range_max
is_prime = [True for i in range(range_max + 1)]
# Cross out all even numbers first.
for i in range(4, range_max, 2):
is_prime[i] = False
primes_count -=1
i = 3
while i * i <= range_max:
if is_prime[i]:
# Update all multiples of this prime number
# CAREFUL: Take note of the range args.
# Reason for i += 2*i instead of i += i:
# Since p and p*p, both are odd, (p*p + p) will be even,
# which means that it would have already been marked before
for multiple in range(i * i, range_max + 1, i * 2):
is_prime[multiple] = False
primes_count -= 1
i += 1
return primes_count
def main():
num_primes = sieve_of_erato(100)
print(num_primes)
if __name__ == "__main__":
main()
</code></pre>
<p>稍后,您可以使用<code>is_prime</code>数组通过简单地检查<code>is_prime[number] == True</code>来检查一个数字是否为素数</p>
<p>如果这不起作用,请尝试<a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve" rel="nofollow noreferrer">segmented sieve</a></p>
<p>另外,您可能会惊讶地发现,有一种方法可以在<code>O(n)</code>而不是<code>O(nloglogn)</code>中生成筛选。检查代码<a href="https://github.com/Anmol-Singh-Jaggi/interview-notes/blob/master/notes/algo-ds-practice/problems/number_theory/sieve_of_eratosthenes/sieve_fastest.py" rel="nofollow noreferrer">here</a></p>