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

Question

在了解了一些SO帖子之后，我发现Eratosthenes的Sieve是生成质数的最佳和最快方法。

我想生成两个数字（例如a和）之间的质数b。

AFAIK，在Sieve方法中，空间复杂度为O（b）。

PS：我写的是Big-O而不是Theta，因为我不知道是否可以减少空间需求。

我们可以降低《蛇神之筛》中的空间复杂度吗？

Answer 1

如果您有足够的空间将所有素数存储到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

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