如何降低Eratosthenes筛中的空间复杂度以在a和b之间生成素数？

如何降低Eratosthenes筛中的空间复杂度以在a和b之间生成素数？

如果您有足够的空间将所有素数存储到sqrt（b），则可以使用额外的空间O（ba）来筛选a到b范围内的素数。

在Python中，它可能类似于：

def primesieve(ps,start,n):  """Sieve the interval [start,start+n) for primes.     Returns a list P of length n.       P[x]==1 if the number start+x is prime.       Relies on being given a list of primes in ps from 2 up to sqrt(start+n)."""  P=[1]*n  for p in ps:    for k in range((-start)%p,n,p):      if k+start<=p: continue      P[k]=0  return P

您只需筛分奇数就可以轻松占用一半的空间。