在 Python 中加速筛选的一个老技巧是使用奇特的 ;-) 列表切片表示法,如下所示。这使用 Python 3。Python 2 所需的更改在注释中注明:
def sieve(n):
"Return all primes <= n."
np1 = n + 1
s = list(range(np1)) # leave off `list()` in Python 2
s[1] = 0
sqrtn = int(round(n**0.5))
for i in range(2, sqrtn + 1): # use `xrange()` in Python 2
if s[i]:
# next line: use `xrange()` in Python 2
s[i*i: np1: i] = [0] * len(range(i*i, np1, i))
return filter(None, s)
在 Python 2 中,这会返回一个列表; Python 3 中的迭代器。在 Python 3 下:
>>> list(sieve(20))
[2, 3, 5, 7, 11, 13, 17, 19]
>>> len(list(sieve(1000000)))
78498
两者都在眨眼间运行。鉴于此,以下是如何构建is_prime
功能:
primes = set(sieve(the_max_integer_you_care_about))
def is_prime(n):
return n in primes
这是set()
使其变得快速的部分。当然,该函数非常简单,您可能想编写:
if n in primes:
直接而不是搞乱:
if is_prime(n):