将埃拉托斯特尼筛法的空间复杂度降至生成范围内质数所需的最小值

Question

在查阅了一些SO帖子后，我发现埃拉托斯特尼筛法是生成质数的最佳且最快的方法。

我想生成两个数字之间的质数，比如a和b。

据我所知，在埃拉托斯特尼筛法中，空间复杂度为O(b)。

附：我写的是大O而不是Theta，因为我不知道空间要求是否可以减少。

我们能否减少埃拉托斯特尼筛法中的空间复杂度？

- Green goblin

---

我认为你只需要2到sqrt(b)之间的质数，因为如果一个数是合数，那么至少其中一个因数必须小于（或等于）sqrt。 （搜索分段筛法以获取更多信息） - Peter de Rivaz

@PeterdeRivaz，我认为你的方法是测试一个数字是否为质数，这与应用筛法算法在给定范围内找到所有质数不同。 [维基百科页面]（http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）将试除法区分为一种单独的技术。因此，这不清楚如何帮助解决原始问题。 - Hew Wolff

你不能从a开始，使用素性测试，然后逐步增加直到达到b吗？ - Realz Slaw

@RealzSlaw 不是这样的。对于非常狭窄的范围，它们是相同的，但对于任何非零宽度，通过奇数筛选比通过奇数测试更快，因为我们测试每个数字，但当我们筛选时，我们跳过越来越长的间隔（例如：9,15,21...或121,143,165...），并且免费收集间隔中的质数。 - Will Ness

@RealzSlaw 好的，正确的应该是(b-a)/log(b)*sqrt(b)/2（对于“短路测试”，所有奇数只用于测试质数，在范围[a..b]中有(b-a)/log(b)个），但结论是相同的。 - Will Ness

Answer 1

这里有两个基本选择：通过小于sqrt(b)的质数筛选范围[a..b]（"偏移"Eratosthenes筛法），或者通过奇数筛选。没错，就像消除每个质数的倍数一样消除每个奇数的倍数。将范围一次性筛选，或者如果范围太宽则分为几个“段”进行筛选（但是如果块太窄，则效率可能会降低）。

在Haskell中，使用可执行伪代码：

-- foldl :: (r -> x -> r) -> r -> [x] -> r     -- type signature of foldl

primesRange_by_Odds a b = 
  foldl (\ r x -> r `minus` [q x, q x+2*x .. b])
        [o, o+2 .. b]                          -- initial value of `r`, the list
        [3, 5 .. floor(sqrt(fromIntegral b))]  -- values of `x`, one after another
  where
    o   = 1 + 2*div a 2                        -- odd start of the range
    q x = x*x - 2*x*min 0 (div (x*x-o) (2*x))  -- 1st odd multiple of x >= x*x in range

通过奇数筛法将额外的空间复杂度增加到 O(1)（除了输出/范围空间O(|b-a|)）。

这是因为我们可以通过迭代添加2来枚举奇数 - 不像埃拉托斯特尼筛法的“核心”素数，其值在sqrt(b)以下，我们必须保留额外的空间O(pi(sqrt(b))) = ~ 2*sqrt(b)/log(b)（其中pi()是素数计数函数）。

剩下的问题是如何找到这些“核心”素数。试除法将需要额外的空间O(1)，但如果我们使用埃拉托斯特尼筛法进行筛选，则需要O(sqrt(b))的空间来执行核心筛选本身 - 除非我们将其作为分段筛子，因此需要辅助空间O(sqrt(sqrt(b)))。选择适合您需求的方法即可。

- Will Ness

Answer 2

如果空间复杂度真的是一个问题，Sorenson Sieve可能值得一看。我从你分享的维基百科页面中得到了这个参考。

- Karan Ashar

---

+1 尽管 Sorensen 不是 Eratosthenes 的变体，而是一种完全不同的筛法，具有更差的时间复杂度和更好的空间复杂度。顺便说一句，通过奇数筛选可能会导致更糟糕的时间复杂度，但它只需要 O(1) 的额外空间（除了输出）。 :) 我也添加了一个关于它的答案。 :) - Will Ness

Answer 3

如果您有足够的空间来存储所有小于sqrt(b)的质数，那么您可以使用额外的O(b-a)空间筛选范围在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

通过仅筛选奇数，您可以轻松将其占用空间减少一半。

- Peter de Rivaz

Answer 4

在您喜欢的搜索引擎上搜索“埃拉托斯特尼筛法”，如果您不想去搜索，我在我的博客上有一个实现。

- user448810